UVA12546_LCM Pair Sum

题目的意思是求 [西伽马(p+q)]其中lcm(p,q)=n。

又见数论呀。

其实这个题目很简单，考虑清楚了可以很简单的方法飘过。

我一开始是这样来考虑的。

对于每一个单独的质因子，如果为p，它的次数为x，那么在p和q中一定有一个为p^x，另一个为p^y（0<=y<=x)，只有这样才能保证lcm为p^x。

这样我们可以枚举第一个为p^x，第二个数就是等比数列求和了。

同时我们再枚举第二个为p^x，这样我们就又是等比数列求和了。。。。

这样我们每次分别计算每一个质因子，同时每一个质因子其实是相对独立的，所以我们最后只要做一次乘法就可以了。不过注意每一个质因子出现的次数哦。

嗯到了这里我们就可以知道了，不过对于每一个答案还是统计了两遍，所以要把多出来的减出来。

嗯，大概就是这样的。

但是A掉后，我好像又秒懂了更更简单的办法。诶，深坑啊。自己考虑考虑就知道啦。。。

这个是经过预处理之后才勉强A掉的，内牛满面啊。。。。。——————————

#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
#define M 1000000007
using namespace std;

ll t,c,p[36],a[36],cas=0;
ll ans;
ll f1[30],f2[30],f3[30];

ll power(ll x,ll y)
{
    ll tot=1;
    while (y)
    {
        if (y&1) tot=(tot*x)%M;
        y>>=1;
        x=(x*x)%M;
    }
    return tot;
}

ll mod(ll x)
{
    if (x<M) return x;
    x-=M;
    if (x<M) return x;
    return x-M;
}

ll count(ll x)
{
    ll A=1,B=1,F,G;
    for (ll i=1; i<=c; i++)
    {
        if (x&(1<<(i-1)))
        {
            F=(f1[i]*(a[i]+1))%M;
            G=((f2[i]-1)*(f3[i]))%M;
        }
        else
        {
            F=((f1[i]-1)*(f3[i]))%M;
            G=(f1[i]*(a[i]))%M;
        }
        A=(A*F)%M;
        B=(B*G)%M; //cout<<" a: & b: "<<A<<' '<<B<<endl;
    }
    return mod(A+B);
}

ll over=power(2,M-2);

int main()
{
    scanf("%lld",&t);
    while (t--)
    {
        ans=0;
        scanf("%lld",&c);
        for (ll i=1; i<=c; i++) scanf("%lld%lld",&p[i],&a[i]);
        for (ll i=1; i<=c; i++)
        {
            f1[i]=power(p[i],a[i]);
            f2[i]=power(p[i],a[i]+1);
            f3[i]=power(p[i]-1,M-2);
        }
        //ans=count(1<<(c)-1);  cout<<"ans : "<<ans<<endl;
        for (ll i=0; i<(1<<c); i++) ans=mod(ans+count(i));
        ll tep=1;
        for (ll i=1; i<=c; i++) tep=(tep*f1[i])%M;
        ans=mod(ans+2*tep);
        ans=(ans*over)%M;
        if (ans<0) ans+=M;
        printf("Case %lld: %lld
",++cas,ans);
    }
    return 0;
}