BZOJ 2956: 模积和

题目

2956: 模积和

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 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。

题解

这道题目我调了好久，有两点错：一是乱用除法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
",Ans%M);
69     return 0;
70 }

View Code