式子自己推出来了,但是一直调不出来,和第一篇题解对了一下式子,是一样的,有没有大佬帮忙调一下代码qwq
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5, mod=20101009;
int prime[N], len;
int mul[N], sum[N];
bool isprime[N];
#define int long long
int fang[N];
inline int get(int n){
return n * (n + 1) %mod * ((mod + 1) / 2) %mod;
}
inline int ope(int A, int B){
int l=1, C=min(A, B), ans=0;
while(l <= C){
int l1=min(A / (A / l), B / (B / l));
ans = (ans + (fang[l1] - fang[l - 1])* get(A / l) %mod * get(B / l) %mod * (sum[l1] - sum[l - 1])) %mod;
l = l1 + 1;
}
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, c;
cin >> n >> m;
c = min(n, m);
mul[1] = 1;
for(int i = 2; i <= c; i++){
if( !isprime[i] ){
prime[++len] = i;
mul[i] = -1;
}
for(int j = 1; j <= len && i * prime[j] <= c; j++){
isprime[i * prime[j]]=1;
if(i % prime[j] == 0){
mul[i * prime[j]] = 0;
break;
}
mul[i * prime[j]] = -mul[i];
}
}
for(int i = 1; i <= c; i++){
sum[i] = sum[i - 1] + mul[i];
fang[i] = (fang[i - 1] + i * i % mod) % mod;
}
int l = 1, ans=0;
while(l <= c){
int l1 = min(n / (n / l), m / (m / l));
ans = (ans + (l + l1) * (l1 - l + 1) %mod * ((mod+1)/2) %mod * ope(n / l, m / l) %mod) %mod;
l = l1 + 1;
}
cout << ans;
return 0;
}