洛谷P2260 [清华集训2012]模积和 题解

题目链接：P2260 [清华集训2012]模积和

题意：

求
( ∑ i = 1 n ∑ j = 1 m ( n   m o d   i ) × ( m   m o d   j ) , i ≠ j ) m o d    19940417 left(sum_{i=1}^{n}sum_{j=1}^{m}(nbmod i)times(mbmod j),ine j right) mod 19940417 (i=1∑n​j=1∑m​(nmodi)×(mmodj),i​=j)mod19940417

根据容斥原理
∑ i = 1 n ∑ j = 1 m ( n   m o d   i ) × ( m   m o d   j ) , i ≠ j = ∑ i = 1 n ∑ j = 1 m ( n   m o d   i ) × ( m   m o d   j ) − ∑ i = 1 n ( n   m o d   i ) × ( m   m o d   i ) sum_{i=1}^{n}sum_{j=1}^{m}(nbmod i)times(mbmod j),ine j \= sum_{i=1}^{n}sum_{j=1}^{m}(nbmod i)times(mbmod j) - sum_{i=1}^{n}(nbmod i)times(mbmod i) i=1∑n​j=1∑m​(nmodi)×(mmodj),i​=j=i=1∑n​j=1∑m​(nmodi)×(mmodj)−i=1∑n​(nmodi)×(mmodi)
然后推推柿子
∑ i = 1 n ∑ j = 1 m ( n   m o d   i ) × ( m   m o d   j ) − ∑ i = 1 n ( n   m o d   i ) × ( m   m o d   i ) = ∑ i = 1 n ( n − i ⌊ n i ⌋ ) × ∑ j = 1 m ( m − j ⌊ m j ⌋ ) − ∑ i = 1 n ( n − i ⌊ n i ⌋ ) × ( m − i ⌊ m i ⌋ ) = ( n 2 − ∑ i = 1 n i ⌊ n i ⌋ ) × ( m 2 − ∑ i = 1 m i ⌊ m i ⌋ ) − ∑ i = 1 n ( n m − m i ⌊ n i ⌋ − n i ⌊ m i ⌋ + i 2 ⌊ n i ⌋ ⌊ m i ⌋ ) = ( n 2 − ∑ i = 1 n i ⌊ n i ⌋ ) × ( m 2 − ∑ i = 1 m i ⌊ m i ⌋ ) − n 2 m + ∑ i = 1 n ( m i ⌊ n i ⌋ + n i ⌊ m i ⌋ − i 2 ⌊ n i ⌋ ⌊ m i ⌋ ) begin{aligned} &sum_{i=1}^{n}sum_{j=1}^{m}(nbmod i)times(mbmod j) - sum_{i=1}^{n}(nbmod i)times(mbmod i) \&=sum_{i=1}^{n}left(n-ileftlfloor{dfrac{n}{i}}rightrfloorright)timessum_{j=1}^{m}left(m-jleftlfloor{dfrac{m}{j}}rightrfloorright) - sum_{i=1}^{n}left(n-ileftlfloor{dfrac{n}{i}}rightrfloorright)timesleft(m-ileftlfloor{dfrac{m}{i}}rightrfloorright) \&=left(n^2-sum_{i=1}^{n}ileftlfloor{dfrac{n}{i}}rightrfloorright)timesleft(m^2-sum_{i=1}^{m}ileftlfloor{dfrac{m}{i}}rightrfloorright)-sum_{i=1}^{n}left(nm-mileftlfloor{dfrac{n}{i}}rightrfloor-nileftlfloor{dfrac{m}{i}}rightrfloor+i^2leftlfloor{dfrac{n}{i}}rightrfloorleftlfloor{dfrac{m}{i}}rightrfloorright) \&=left(n^2-sum_{i=1}^{n}ileftlfloor{dfrac{n}{i}}rightrfloorright)timesleft(m^2-sum_{i=1}^{m}ileftlfloor{dfrac{m}{i}}rightrfloorright)-n^2m+sum_{i=1}^{n}left(mileftlfloor{dfrac{n}{i}}rightrfloor+nileftlfloor{dfrac{m}{i}}rightrfloor-i^2leftlfloor{dfrac{n}{i}}rightrfloorleftlfloor{dfrac{m}{i}}rightrfloorright) end{aligned} ​i=1∑n​j=1∑m​(nmodi)×(mmodj)−i=1∑n​(nmodi)×(mmodi)=i=1∑n​(n−i⌊in​⌋)×j=1∑m​(m−j⌊jm​⌋)−i=1∑n​(n−i⌊in​⌋)×(m−i⌊im​⌋)=(n2−i=1∑n​i⌊in​⌋)×(m2−i=1∑m​i⌊im​⌋)−i=1∑n​(nm−mi⌊in​⌋−ni⌊im​⌋+i2⌊in​⌋⌊im​⌋)=(n2−i=1∑n​i⌊in​⌋)×(m2−i=1∑m​i⌊im​⌋)−n2m+i=1∑n​(mi⌊in​⌋+ni⌊im​⌋−i2⌊in​⌋⌊im​⌋)​
有一个小的公式，这里就不证明了（逃
∑ i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 sum_{i=1}^{n}i^2 = dfrac{n(n+1)(2n+1)}{6} i=1∑n​i2=6n(n+1)(2n+1)​
然后到这里就没啥难度了

考虑数论分块

代码如下

#include 
using namespace std;
#define int long long
const int p=19940417;
const int inv2=9970209;
const int inv6=3323403;
#define sum1(x) ((x)%p*(x+1)%p*inv2%p)
#define sum2(x) ((x)%p*(x+1)%p*(2*(x)%p+1)%p*inv6%p)
int solve(int x)
{
    int res=x%p*x%p;
    for(int l=1,r; l<=x; l=r+1)
    {
        r=x/(x/l);
        res=(res-(sum1(r)-sum1(l-1))%p*(x/l)%p)%p;
    }
    return res;
}
int n,m,a,b,c,ans;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    if(n>m)swap(n,m);
    ans=(solve(n)*solve(m)%p-n%p*n%p*m%p)%p;
    for(int l=1,r; l<=n; l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        a=(a+(sum1(r)-sum1(l-1))%p*m%p*(n/l)%p)%p;
        b=(b+(sum1(r)-sum1(l-1))%p*n%p*(m/l)%p)%p;
        c=(c+(sum2(r)-sum2(l-1))%p*(n/l)%p*(m/l)%p)%p;
    }ans=((ans+a+b-c)%p+p)%p;
    cout << ans << endl;
    return 0;
}

转载请说明出处