首页 > 代码库 > bzoj 1257: [CQOI2007]余数之和sum

bzoj 1257: [CQOI2007]余数之和sum

这是个神题233(一开始想的也差不多,然而不知道为什么觉得复杂度不对,(没想到等差数列,就GG掉了))

一个数k,k/x=y...?,?构成等差数列,直接o(1)解决,每得出一个y的区间,是[i,last](last见程序,至于为什么,写写看看,挺显然的)

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 #define ls tr[x][0]
 6 #define rs tr[x][1]
 7 using namespace std;
 8 inline int ra()
 9 {
10     int x=0,f=1; char ch=getchar();
11     while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}
12     while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
13     return x*f;
14 }
15 int main()
16 {
17     int n=ra(),k=ra();
18     int last,lmt=min(n,k),d;
19     LL tem,ans=0;
20     if (n>k) ans=(LL)k*(n-k);
21     for (int i=1; i<=lmt; i=last+1)
22     {
23         d=k/i;
24         last=min(k/d,lmt);
25         tem=last-i+1;
26         ans+=tem*(k%i)-(tem*(tem-1)>>1)*d;
27     }
28     cout<<ans;
29     return 0;
30     
31 }

 

bzoj 1257: [CQOI2007]余数之和sum