首页 > 代码库 > BZOJ 2956: 模积和
BZOJ 2956: 模积和
题目
2956: 模积和
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 554 Solved: 257
[Submit][Status]
Description
求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。
Input
第一行两个数n,m。
Output
一个整数表示答案mod 19940417的值
Sample Input
3 4
Sample Output
1
样例说明
答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1
数据规模和约定
对于100%的数据n,m<=10^9。
样例说明
答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1
数据规模和约定
对于100%的数据n,m<=10^9。
题解
这道题目我调了好久，有两点错：一是乱用除法QAQ，要乘逆元才对！二是错误的估计了结果的大小，少用了几个%。虽然取模的数很小，但是两个乘在一起照样让你爆精度！每步都要取模！
这题的思路是分别计算∑∑((n mod i)*(m mod j))和∑∑((n mod i)*(m mod j))[i==j]的值，并且作差。
最后化简得式子是
∑∑((n mod i) * (m mod j)) 1<=i<=n, 1<=j<=m, i≠j=
∑(n mod i) * ∑(m mod i) - ∑((n mod i) * (m mod i))=
∑(n-[n/i]*i) * ∑(m-[m/i]*i) - ∑(nm-([n/i]+[m/i])i+[n/i][m/i]*i*i)【右式中[]表示下取整】
代码
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 const long long M=19940417; 6 7 long long n,m; 8 9 10 inline int remin(int a,int b){11 if (a<b) return a;12 return b;13 }14 15 inline long long sum(long long n){ 16 return n*(n+1)%M*(2*n+1)%M*3323403%M; 17 } 18 19 inline long long getDist(int x,int y){20 return (x+y)%M*(y-x+1)%M*9970209%M;21 } 22 23 inline long long getOneAns(long long x){24 long long ans=((long long)x*(long long)x)%M;25 long long pos;26 for (long long i=1;i<=x;i=pos+1){27 pos=remin(x/(x/i),x);28 //cout<<"+"<<(long long)x*(long long)(pos-i+1)%M<<endl;29 //cout<<"-"<<((long long)((long long)(pos)*(long long)(pos+1)/(long long)2-(long long)(i-1)*(long long)(i)/(long long)2)*(long long)(x/i))%M<<endl;30 //cout<<"x"<<(long long)(pos)*(long long)(pos+1)/(long long)2-(long long)(i-1)*(long long)(i)/(long long)2<<endl;31 //ans=ans-((long long)getDist(i,pos)%M*(long long)(x/i))%M;32 ans-=(x/i)*getDist(i,pos)%M;33 while(ans<0) ans+=M;34 }35 //cout<<endl;36 while(ans<0) ans+=M;37 return ans;38 } 39 40 inline long long getTwoAns(long long x1,long long x2){41 long long ans=0;42 long long pos;43 long long x=remin(x1,x2);44 ans=x%M*x1%M*x2%M;45 for (long long i=1;i<=x;i=pos+1){46 pos=remin(x1/(x1/i),x2/(x2/i));47 //cout<<"POS"<<i<<"~"<<pos<<endl;48 //cout<<"+"<<(long long)(pos-i+1)*(long long)x1*(long long)x2<<endl;49 //cout<<"-"<<(long long)x1*(long long)(x2/i)*getDist(i,pos)<<endl;50 ///cout<<"-"<<(long long)x2*(long long)(x1/i)*getDist(i,pos)<<endl;51 //cout<<"+"<<((long long)((long long)x1/(long long)i)*(long long)((long long)x2/(long long)i))*getSDist(i,pos)<<endl;52 //cout<<"————————————"<<endl;53 ans=ans-(long long)x1%M*(long long)(x2/i)%M*getDist(i,pos)%M-(long long)x2%M*(long long)(x1/i)%M*getDist(i,pos)%M+((long long)((long long)x1/(long long)i)%M*(long long)((long long)x2/(long long)i))%M*(sum(pos)-sum(i-1))%M;54 while(ans<0) ans+=M;55 }56 while(ans<0) ans+=M;57 return ans;58 }59 60 int main(){61 scanf("%lld%lld",&n,&m);62 long long Ans=((long long)getOneAns(n)*(long long)getOneAns(m))%M;63 Ans-=getTwoAns(n,m);64 //cout<<getOneAns(n)<<endl;65 //cout<<getOneAns(m)<<endl;66 //cout<<getTwoAns(n,m)<<endl;67 while(Ans<0) Ans+=M;68 printf("%lld\n",Ans%M);69 return 0;70 }
BZOJ 2956: 模积和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。