题解 P2261 【[CQOI2007]余数求和】

· · 题解

标准数学题 三个小时才做出来

说实话题意我都看了半天= = 关键是k不变 mod从1到n

第一幕： 暴力 O(n)算法 TLE 4组 （这年头也只有数学题才能把O(n)搞T了，不过60分暴力，还要标程干嘛= =）

第二幕： 对于n>k的优化 发现原题中一串5不用一个一个算 一起算会快很多 但是还是TLE 4组（说明这个优化并没有给分= =）

第三幕： 打了一个100 20的表把k mod i（1<=i<=n）看了看 0 0 2 0 0 2 6 4 2 0 9 8 7 6 5 4 3 2 1 0 woc后面一堆9,8,7，。。1显然直接算嘛

大概是从k mod (k/2)+1 开始一直到 k mod k （也就是k/1）是一个等差数列这样可以优化 但是没自己实现 看题解去了

第四幕：看题解看了一个小时就是看不懂 根据自己原来的方式 继续分块 分为

          k mod k ~ k mod (k/2)+1

          k mod (k/2) ~ k mod (k/3)+1

          k mod (k/3) ~ k mod (k/4)+1

. . . . . . . .

          k mod (k/(k-1)) ~ k mod (k/k)+1

k mod k /k

可以这样算是因为= = 那一块里面 比如对于上面第三组 k/3 ~ k/4+1 的任意一个i， k/i都等于3（因为是整除嘛 所以余数是一个等差数列 可以直接求和（我开始怀疑高斯在信息学方面是不是有造诣） 但是这样搞的话 有k部分 时间复杂度O(k) 还是TLE

第五幕：沃日我都快疯了搞了四次都过不去 然后我把上面省略号展开了一下 为了以100 20的数据对上号 这样吧= =我画一个k=20的图（沃日洛谷我不会传图，将就看看）

0 0 2 0 0 2 6 4 2 0 9 8 7 6 5 4 3 2 1 0

_______ __________________

20/3+1 20/2 20/2+1 20/1(这一行表示的是端点为第几个数)

上面这列数中从左往右数第x个等于20%x（就相当于一个1~20的数列，用20挨着挨着去mod一次）

然后呢？ 应该是20/4+1 ~ 20/3了对吧？ 但是实际上呢？ 20/4+1=6 20/3=6意思是这一段只有一个数！！！！！

（所以前面6个我一直没看出来规律） 所以最前面的6个数直接算是比分块要快的！而且也会出问题，比如说 20/20+1~20/19

就出现右边界小于左边界的情况，所以前6个应该直接算，后面再分块，这样的话，对于20来说，算了6+2=8次看起来挺高效的啊！那对于任意的k我怎么知道前几个直接算呢？貌似是这样的，假设k还是20 考虑当分块有意义的时候k/i+1<=k/(i-1)

貌似是i最大取4，神犇们根据数学方法证明这个点就是(int)(sqrt(k)) 我YY了一下感觉是对的，那就这样写吧。（注：为什么是4而不是6 ?因为4只是要求分块有意义即可，6是要求那一段数至少有两个）

这样的话代码就出来了（我滴天省选级别的数学题到底有好难）（而且数学题就是分析过程多么长，程序多么短，这题才40行）

（妈呀写了这么多，我觉得我讲的已经够清楚了吧= =）


#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long sum=0;
    int k,n;cin>>n>>k;
    for(int i=2;i<=(int)(sqrt(k))&&i<=n;i++)//  k%1必定=0不用算  另外n有可能小于(int)(sqrt(k))要加一个&&判断
      sum+=(k%i);
    if(n<=(int)(sqrt(k)))                                    //对于这种情况直接输出去
    {
        printf("%lld",sum);return 0;
    }
    int sp=k/(int)(sqrt(k))+1;                         //sp表示的是左端点k要除的那个数，这里+1是为了跟下面--sp对接一下 实际上第一块左端点是(int)(sqrt(k))+1 实际上的sp为k/(int)(sqrt(k))  (第一个sp是根据左端点计算出来的)
    int start,last;
    for(;;)
    {
        if(--sp==1)break;
        start=k/sp+1,last=k/(sp-1);    //  start和last指示的是原来1~n数列中的一段数
        if(start>n) break;
        last=min(last,n);
        if(start==last)                  //单个数直接计算  （好像不要这个if也可以做）
        {
            sum+=(k%start);continue;
        }
        int first=k%start;            //first和end指示的是MOD 之后的数列中的一段数  跟上面start和last容易搞混 
        int end=k%last; 
        int much=last-start+1;//求和之前先把项数搞出来  因为1~n的数列公差为1，故为last-start+1
        sum+=(long long)(first+end)*much/2;//注意强制转换long long要不然会爆int
    }
    if(n>k) sum+=(long long)(n-k)*k;// 注意强制转换  计算 n>k部分的余数(全为k)
    printf("%lld",sum);
    return 0;
}