BZOJ 3560 DZY Loves Math V 数论

题目大意：给定a1,a2,...,an,求

由于φ是积性函数，我们可以将i1i2...in分解质因数，对于每个质因数分开讨论，求积即可

将每个a分解质因数，假设分解后某个质数p在每个ai中的次数分别是bi，那么p对答案的贡献就是

于是对p^j维护一个前缀和，直接计算即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct abcd{
    int p,a;
    bool operator < (const abcd &x) const
    {
        if(p!=x.p)
            return p<x.p;
        return a<x.a;
    }
}prime_factors[1001001];
int n,tot;
long long ans=1;
void Decomposition(int x)
{
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0)
        {
            prime_factors[++tot].p=i;
            while(x%i==0)
                prime_factors[tot].a++,x/=i;
        }
    if(x^1)
        prime_factors[++tot].p=x,prime_factors[tot].a=1;
}
long long Quick_Power(long long x,long long y)
{
    long long re=1;
    while(y)
    {
        if(y&1) (re*=x)%=MOD;
        (x*=x)%=MOD;y>>=1;
    }
    return re;
}
void Calculate(int l,int r)
{
    static long long sum[30];
    long long p=prime_factors[l].p;
    long long re=1;
    int i;
    sum[0]=1;
    for(i=1;i<=prime_factors[r].a;i++)
        sum[i]=sum[i-1]*p%MOD;
    for(i=1;i<=prime_factors[r].a;i++)
        (sum[i]+=sum[i-1])%=MOD;
    for(i=l;i<=r;i++)
        (re*=sum[prime_factors[i].a])%=MOD;
    re--;(re*=Quick_Power(p,MOD-2))%=MOD;
    (re*=p-1,++re)%=MOD;
    (ans*=re)%=MOD;
}
int main()
{
    int i,x;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        Decomposition(x);
    }
    sort(prime_factors+1,prime_factors+tot+1);
    for(i=1;i<=tot;i++)
    {
        static int last;
        if(i==tot||prime_factors[i].p!=prime_factors[i+1].p)
            Calculate(last+1,i),last=i;
    }
    cout<<(ans%MOD+MOD)%MOD<<endl;
    return 0;
}

BZOJ 3560 DZY Loves Math V 数论

原文：http://blog.csdn.net/popoqqq/article/details/42739963