BZOJ2154: Crash의 숫자 표 & BZOJ2693: jzptab

[전송문: BZOJ2154 & BZOJ2693]

제목 요약:

n, m을 주고 $\sum 를 구합니다.{i=1}^{n}\sum_{j=1}^{m}LCM(i,j)$

문제 풀이:

모비우스 반전(BZOJ2693은 여러 그룹의 데이터이기 때문에 데이터가 강하기 때문에 코드는 BZOJ2693의)
n 원형이 $\sum 인 경우 설정{i=1}^{n}\sum_{j=1}^{m}i*j/gcd(i,j)$
그리고 d값을 i와 j의 gcd로 매거하여 $$\sum{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{d}[gcd(i,j)==d]$$
gcd(i,j)==d이기 때문에 gcd(i/d,j/d)===1,$$\sum 획득{d=1}^{n}d*\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}i*j[gcd(i,j)==1]$$
모반의 성질:$\sum{d|x}\mu(d)=[x==1]$이므로 $$\sum{d=1}^{n}d*\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}i*j*\sum_{t|gcd(i,j)}\mu(t)$$
교환 및 수취 $$\sum{d=1}^{n} d*\sum_{t=1}^{\frac{n}{d}}\mu(t) *\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}} i*j[gcd(i,j)==t]$$
　　$$\sum_{d=1}^{n}d*\sum_{t=1}^{\frac{n}{d}}t^{2}*\mu(t)*\sum_{i=1}^{\frac{n}{dt}}\sum_{j=1}^{\frac{m}{dt}}i*j$$
$T=dt$, $S(x)=\sum 설정{i=1}^{x}i$, $$\sum 획득{d=1}^{n}\sum_{t=1}^{\frac{n}{d}}T*t*\mu(t)*S(\frac{n}{T})*S(\frac{m}{T})$$
$S(\rac{n} {T})*S(\rac{m} {T})$를 앞당겨 $$\sum 를 획득{T=1}^{n}T*S(\frac{n}{T})*S(\frac{m}{T})\sum_{d|T}d*\mu(d)$$
$S(\rac{n} {T})*S(\rac{m} {T})$는 접두어와 미리 처리할 수 있기 때문에 $\sum 를{d|T}d*\mu(d)$빠르게 구하면 됩니다.
$F(T)=\sum 설정{d|T}d*\mu(d)$, 분명히 적성 함수입니다. 온라인으로 체질할 때 구하면 됩니다
그리고 $T*F(T)$를 접두어와 합을 구한 다음 블록 가속을 제거하면 지나갈 수 있습니다

참조 코드:

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
int prime[11000000],v[11000000];
LL f[11000000],sum[11000000];
LL Mod=1e8+9;
void pre(int n)
{
    f[1]=1;
    int tot=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=i;
            prime[++tot]=i;
            f[i]=(1-i+Mod)%Mod;
        }
        for(int j=1;j<=tot;j++)
        {
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            if(i%prime[j]==0){f[i*prime[j]]=f[i]%Mod;break;}
            else f[i*prime[j]]=f[i]*f[prime[j]]%Mod;
        }
    }
    for(int i=1;i<=n;i++) f[i]=(f[i]*LL(i)%Mod+f[i-1])%Mod;
    for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+LL(i))%Mod;
}
int main()
{
    pre(10000000);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        LL ans=0;
        for(int i=1,j;i<=n;i=j+1)
        {
            j=min(n/(n/i),m/(m/i));
            ans=(ans+(f[j]-f[i-1]+Mod)%Mod*sum[n/i]%Mod*sum[m/i]%Mod)%Mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}

 

전재 대상:https://www.cnblogs.com/Never-mind/p/9845948.html