bzoj 2956: 模积和 —

Description

　求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。

Input

第一行两个数n,m。

Output

　　一个整数表示答案mod 19940417的值

Sample Input

3 4

Sample Output

样例说明
答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) +

(3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1
数据规模和约定
　　对于100%的数据n,m<=10^9。

————————————————————————————————

$这道题\space 就很复杂QAQ$
$我们先不考虑 i==j 的情况 $
$题目等价于 \sum _{i=1} ^n n-\lfloor \frac{n}{i} \rfloor*i$
$可以转换为 n^2-\sum _{i=1} ^n \lfloor \frac{n}{i} \rfloor*i$
$现在我们可以来考虑i==j的情况了 $
$这个东西我们可以变成 \sum_{i=1}^ {k=min(n,m)} (n-\lfloor \frac{n}{i} \rfloor *i)*(m-\lfloor \frac{m}{i} \rfloor)$
$我们可以把他拆出来$

$变成k*n*m-m\sum_{i=1}^k \lfloor \frac{n}{i} \rfloor*i-n\sum_{i=1}^k \lfloor \frac{m}{i} \rfloor*i + \sum_{i=1}^k \lfloor \frac{n}{i} \rfloor *\lfloor \frac{m}{i} \rfloor$

$这样就可以AC辣 $

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using std::min;

const int mod=,P=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL n,m;

LL calc(LL n,LL k){

    LL ans=;

    for(LL L=,R=;L<=k;L=R+) R=min(k,n/(n/L)),ans=(ans+(L+R)*(R-L+)/%mod*(n/L))%mod;

    return ans;

}

LL F(LL x){return x*(x+)%mod*(*x+)%mod*P%mod;}

int main(){

    n=read(); m=read();

    LL ans=(n*n-calc(n,n))%mod*((m*m-calc(m,m))%mod)%mod,k=min(n,m);

    ans=(ans-k*n%mod*m)%mod;

    ans=(ans+m*calc(n,k))%mod;

    ans=(ans+n*calc(m,k))%mod;

    for(LL L=,R=,s0=,s1;L<=k;L=R+){

        R=min(m/(m/L),n/(n/L));

        R=min(R,k);

        s1=F(R);

        ans=(ans-(n/L)*(m/L)%mod*(s1-s0))%mod;

        s0=s1;

    }

    printf("%lld\n",(ans+mod)%mod);

    return ;

}

Tips 求类似 $\sum _{i=1} ^n \lfloor \frac{n}{i} \rfloor*i$

我们可以利用程序内calc的写法就可以辣2333

巴特西

bzoj 2956: 模积和 ——数论

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章