A1231. Crash的数字表格(贾志鹏)

时间限制：2.0s 内存限制：512.0MB

总提交次数：410 AC次数：154 平均分：63.93

将本题分享到：

试题来源

　　2011中国国家集训队命题答辩

问题描述

　　今天的数学课上，Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b，LCM(a, b)表示能同时整除a和b的最小正整数。例如，LCM(6, 8) = 24。
　　回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张N*M的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i, j)。一个4*5的表格如下：

　　看着这个表格，Crash想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当N和M很大时，Crash就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大，Crash只想知道表格里所有数的和mod20101009的值。

输入格式

　　输入的第一行包含两个正整数，分别表示N和M。

输出格式

　　输出一个正整数，表示表格中所有数的和mod20101009的值。

样例输入

4 5

样例输出

122

数据规模和约定

　　30%的数据满足N, M≤ 103。
　　70%的数据满足N, M≤ 105。
　　100%的数据满足N, M≤ 107。

参考：http://blog.csdn.net/regina8023/article/details/44243911

表示看不懂代码

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=1e7+;

const int mod=;

int n,m,tot,mu[N],prime[N/];bool check[N];

ll sum[N];

void mobius(){

    mu[]=;

    for(int i=;i<=n;i++){

        if(!check[i]) prime[++tot]=i,mu[i]=-;

        for(int j=;j<=tot&&i*prime[j]<=n;j++){

            check[i*prime[j]]=;

            if(!(i%prime[j])){mu[i*prime[j]]=;break;}

            else mu[i*prime[j]]=-mu[i];

        }

    }

    for(int i=;i<=n;i++) sum[i]=sum[i-]+(1LL*mu[i]*i%mod*i%mod);

}

ll SUM(ll x,ll y){

    x=(x*(x+)>>)%mod;

    y=(y*(y+)>>)%mod;

    return (x*y%mod);

}

ll GET(ll x,ll y){

    ll res=;

    int pos=;

    for(int i=;i<=x;i=pos+){

        pos=min(x/(x/i),y/(y/i));

        res=(res+(sum[pos]-sum[i-]+mod)%mod*SUM(x/i,y/i)%mod)%mod;

    }

    return res;

}

int main(){

    scanf("%d%d",&n,&m);

    if(n>m) swap(n,m);

    mobius();

    ll ans=;

    int pos=;

    for(int i=;i<=n;i=pos+){

        pos=min(n/(n/i),m/(m/i));

        ans=(ans+(1LL*(i+pos)*(pos-i+)>>)%mod*GET(n/i,m/i)%mod)%mod;

    }

    printf("%lld",ans);

    return ;

}

巴特西

A1231. Crash的数字表格(贾志鹏)

最新文章

热门文章