http://www.lydsy.com/JudgeOnline/problem.php?id=2956

---

　求∑∑((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。

---

朴素算法O（n*m）

#include #include #include #include #include using namespace std; const int Mod = 19940417; const int Maxn = 1e9; int n,m; int main(void) { ios::sync_with_stdio(false); cin>>n>>m; int ans = 0; for(int i=1;i<=n;i++) { int x = n % i; for(int j=1;j<=m;j++) { if(i==j)continue; int y = m % j; ans = (ans+(long long)x*y)%Mod; } } cout<return 0; }

---

进一步思考

首先想到，要对式子进行一定的代数变形。 对于n%i=n−⌊ni⌋∗i
∑∑(n%i)(m%j)(i≠j)∑∑[n−⌊ni⌋∗i][m−⌊mj⌋∗j](i≠j)
代码: C++ #include #include #include #include #include #include #include #define inf 1000000000 #define mod 19940417 #define ine 3323403 #define ll long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll n,m,ans; ll sum(ll a,ll b) { return (b-a+1)*(a+b)/2%mod; } ll sum2(ll x) { return x*(x+1)%mod*(2*x+1)%mod*ine%mod; } ll cal(ll n) { ll tmp=0; for(ll i=1,j;i<=n;i=j+1) { j=n/(n/i); tmp=(tmp+n*(j-i+1)%mod-sum(i,j)*(n/i))%mod; } return (tmp+mod)%mod; } int main() { n=read();m=read(); ans=cal(n)*cal(m)%mod; if(n>m)swap(n,m); ll s1,s2,s3; for(int i=1,j;i<=n;i=j+1) { j=min(n/(n/i),m/(m/i)); s1=n*m%mod*(j-i+1)%mod; s2=(n/i)*(m/i)%mod*(sum2(j)-sum2(i-1)+mod)%mod; s3=(n/i*m+m/i*n)%mod*sum(i,j)%mod; ans=(ans-(s1+s2-s3)%mod+mod)%mod; } printf("%lld ",ans); return 0; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include #include #include #include #include #include #include #define inf 1000000000 #define mod 19940417 #define ine 3323403 #define ll long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll n,m,ans; ll sum(ll a,ll b) { return (b-a+1)*(a+b)/2%mod; } ll sum2(ll x) { return x*(x+1)%mod*(2*x+1)%mod*ine%mod; } ll cal(ll n) { ll tmp=0; for(ll i=1,j;i<=n;i=j+1) { j=n/(n/i); tmp=(tmp+n*(j-i+1)%mod-sum(i,j)*(n/i))%mod; } return (tmp+mod)%mod; } int main() { n=read();m=read(); ans=cal(n)*cal(m)%mod; if(n>m)swap(n,m); ll s1,s2,s3; for(int i=1,j;i<=n;i=j+1) { j=min(n/(n/i),m/(m/i)); s1=n*m%mod*(j-i+1)%mod; s2=(n/i)*(m/i)%mod*(sum2(j)-sum2(i-1)+mod)%mod; s3=(n/i*m+m/i*n)%mod*sum(i,j)%mod; ans=(ans-(s1+s2-s3)%mod+mod)%mod; } printf("%lld ",ans); return 0; }

---

Latex忽略代码中的空格
不等号: eq
空格 : quad
换行:
向下取整:lfloor{ } floor