current position:Home>Module product and problem solution of Luogu p2260 [Tsinghua training 2012]

Module product and problem solution of Luogu p2260 [Tsinghua training 2012]

2022-05-15 07:27:16q779

Luogu P2260 [ Tsinghua training 2012] Modular product sum Answer key

Topic link :P2260 [ Tsinghua training 2012] Modular product sum

The question

seek
( ∑ 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}(n\bmod i)\times(m\bmod j),i\ne j \right) \mod 19940417 (i=1nj=1m(nmodi)×(mmodj),i=j)mod19940417

According to the principle of inclusion and exclusion
∑ 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}(n\bmod i)\times(m\bmod j),i\ne j \\= \sum_{i=1}^{n}\sum_{j=1}^{m}(n\bmod i)\times(m\bmod j) - \sum_{i=1}^{n}(n\bmod i)\times(m\bmod i) i=1nj=1m(nmodi)×(mmodj),i=j=i=1nj=1m(nmodi)×(mmodj)i=1n(nmodi)×(mmodi)
Then push the persimmon
∑ 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}(n\bmod i)\times(m\bmod j) - \sum_{i=1}^{n}(n\bmod i)\times(m\bmod i) \\&=\sum_{i=1}^{n}\left(n-i\left\lfloor{\dfrac{n}{i}}\right\rfloor\right)\times\sum_{j=1}^{m}\left(m-j\left\lfloor{\dfrac{m}{j}}\right\rfloor\right) - \sum_{i=1}^{n}\left(n-i\left\lfloor{\dfrac{n}{i}}\right\rfloor\right)\times\left(m-i\left\lfloor{\dfrac{m}{i}}\right\rfloor\right) \\&=\left(n^2-\sum_{i=1}^{n}i\left\lfloor{\dfrac{n}{i}}\right\rfloor\right)\times\left(m^2-\sum_{i=1}^{m}i\left\lfloor{\dfrac{m}{i}}\right\rfloor\right)-\sum_{i=1}^{n}\left(nm-mi\left\lfloor{\dfrac{n}{i}}\right\rfloor-ni\left\lfloor{\dfrac{m}{i}}\right\rfloor+i^2\left\lfloor{\dfrac{n}{i}}\right\rfloor\left\lfloor{\dfrac{m}{i}}\right\rfloor\right) \\&=\left(n^2-\sum_{i=1}^{n}i\left\lfloor{\dfrac{n}{i}}\right\rfloor\right)\times\left(m^2-\sum_{i=1}^{m}i\left\lfloor{\dfrac{m}{i}}\right\rfloor\right)-n^2m+\sum_{i=1}^{n}\left(mi\left\lfloor{\dfrac{n}{i}}\right\rfloor+ni\left\lfloor{\dfrac{m}{i}}\right\rfloor-i^2\left\lfloor{\dfrac{n}{i}}\right\rfloor\left\lfloor{\dfrac{m}{i}}\right\rfloor\right) \end{aligned} i=1nj=1m(nmodi)×(mmodj)i=1n(nmodi)×(mmodi)=i=1n(niin)×j=1m(mjjm)i=1n(niin)×(miim)=(n2i=1niin)×(m2i=1miim)i=1n(nmmiinniim+i2inim)=(n2i=1niin)×(m2i=1miim)n2m+i=1n(miin+niimi2inim)
There is a small formula , There's no proof ( flee
∑ 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=1ni2=6n(n+1)(2n+1)
Then there's no difficulty here

Consider number theory blocking

The code is as follows

#include <bits/stdc++.h>
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;
}

Reprint please explain the source

copyright notice
author[q779],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/131/202205102141448432.html

Random recommended