首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。