60pts取模求助
查看原帖
60pts取模求助
754746
Resolute_Faith楼主2022/7/25 17:27

那玩意不是质数,到底应该怎么对那个平方和取模啊,试了各种方法都不行

#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define fir first
#define sec second
#define lowbit(i) (i&(-i))
using namespace std;
const int N=5e5+5;
const double pi=acos(-1);
const int inf=1e18;
const int mod=19940417;
struct edge{int to,nxt,l;};
int n,m;
inline int read(){
    char op=getchar();
    int w=0,s=1;
    while(op<'0'||op>'9'){
        if(op=='-') s=-1;
        op=getchar();
    }
    while(op>='0'&&op<='9'){
        w=(w<<1)+(w<<3)+op-'0';
        op=getchar();
    }
    return w*s;
}
signed main(){
    n=read(),m=read();
    if(n>m) swap(n,m);
    int ansx=0;
    for(register int i=1;i<=n;){
        int l=i,r=n/(n/i);
        ansx=(ansx+((r-l+1)*(l+r)/2%mod*(n/l)%mod)%mod)%mod;
        i=r+1;
    }
    int ansy=0;
    for(register int i=1;i<=m;){
        int l=i,r=m/(m/i);
        ansy=(ansy+((r-l+1)*(l+r)/2%mod*(m/l)%mod)%mod)%mod;
        i=r+1;
    }
    int ans=(((n%mod*n%mod)%mod*m%mod)%mod*m%mod)%mod;
    ans=(ans-((m%mod*m%mod)%mod*ansx%mod)%mod+mod)%mod;
    ans=(ans-((n%mod*n%mod)%mod*ansy%mod)%mod+mod)%mod;
    ans=(ans+(ansx%mod*ansy%mod)%mod)%mod;
    ans=(ans-((n%mod*n%mod)%mod*m%mod)%mod+(m%mod*ansx%mod)%mod+mod)%mod;
    int ansz=0;
    for(register int i=1;i<=n;){
        int l=i,r=m/(m/i);
        r=min(r,n);
        ansz=(ansz+((r-l+1)*(l+r)/2%mod*(m/l)%mod)%mod)%mod;
        i=r+1;
    }
    ans=(ans+(n%mod*ansz%mod)%mod)%mod;
    int answ=0;
    for(register int i=1;i<=n;){
        int l=i,r=min(m/(m/i),n/(n/i));
        r=min(r,n);
        answ=(answ+((((r*(r+1)*(2*r+1))/6-((l-1)*l*(2*l-1))/6)%mod*(n/l)%mod)%mod*(m/l)%mod)%mod)%mod;
        i=r+1;
    }//Here
    ans=(ans-answ+mod)%mod;
    printf("%lld",ans);
}
2022/7/25 17:27
加载中...