求助莫反,悬赏3关注
查看原帖
求助莫反,悬赏3关注
538427
czy0323楼主2023/5/21 11:59

式子自己推出来了,但是一直调不出来,和第一篇题解对了一下式子,是一样的,有没有大佬帮忙调一下代码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;
}
2023/5/21 11:59
加载中...