P2260 [清华集训2012]模积和

Dear 丶 2021-11-17 08:10 222阅读 0赞

终于会用$\\LaTeX$和Typora啦

$$  
\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{m\}(n\\%i)(m\\%j)  
$$  
即

$$  
\\begin\{align\}  
&\\sum\_\{i=1\}^\{n\}n\\%i\\sum\_\{j=1\}^\{m\}m\\%j\\\\  
&=\\sum\_\{i=1\}^\{n\}(n-\\lfloor n/i \\rfloor \*i)\\sum\_\{j=1\}^\{m\}(m-\\lfloor m/j \\rfloor \*j)  
\\end\{align\}  
$$

又有i$\\neq$j

所以还要求  
$$  
\\begin\{align\}  
\\sum\_\{i=1\}^\{min(n,m)\}(n-\\lfloor n/i \\rfloor \*i)(m-\\lfloor m/i \\rfloor \*i)  
\\end\{align\}  
$$  
展开求，加的项可以直接等差和分块求

涉及$i^2$的项可以用平方求和公式：  
$$  
\\sum\_\{i=1\}^\{n\}i^\{2\}=\\frac\{n(n+1)(2n+1)\}\{6\}  
$$  
由于本题模数不是质数，不可以用费马小定理解逆元，要先用exgcd或欧拉定理解出inv6

宁可多$\\% $也不要少$\\% $

#include<bits/stdc++.h>
    using namespace std;
    const int p=19940417;
    const int inv6=3323403;
    typedef long long ll;
    int n,m;
    ll ans1,ans2,ans3,ans;
    ll qsum(ll n){
        return ((n*(n+1))%p*(2*n+1)%p*inv6)%p;
    }
    int main(){
        cin>>n>>m;
        ans1=(ll)n%p*n%p;
        ans2=(ll)m%p*m%p;
        for(int i=1;i<=n;i++){
            int t=n/i,j=n/t;
            ans1-=((ll)(i+j)*(j-i+1)/2%p)*t;    
            i=j;
            ans1%=p;
        }
        for(int i=1;i<=m;i++){
            int t=m/i,j=m/t;
            ans2-=((ll)(i+j)*(j-i+1)/2%p)*t;
            i=j;
            ans2%=p;    
        }
        ans3=((ll)min(n,m)*n%p)*m;
        for(int i=1;i<=min(n,m);i++){
            int t1=n/i;
            int t2=m/i;
            int j=min(n/t1,m/t2);
            ans3-=((ll)(i+j)*(j-i+1)/2*t1%p)*m%p;
            ans3-=((ll)(i+j)*(j-i+1)/2*t2%p)*n%p;
            ans3+=((ll)(qsum(j)-qsum(i-1))*t1%p)*t2;
            i=j;
            ans3=(ans3%p+p)%p;
        }
        ans=(ans1*ans2%p-ans3+p)%p;
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Hikigaya/p/11239281.html