hdu 1695 gcd(Mobius逆転)

モビウスの再演資料http://wenku.baidu.com/view/542961fdba0d4a7302763ad5.html
http://baike.baidu.com/link?url=1qQ-hkgOwDJ AH 4 xyRcEQVoOTm HbiRCyZ-hEJxRBQ 8 G 0 OurXNr 6 Rh 6 pYJ 9 fhySI 0 MY 2 RKpcaSPV 9 X 75 mQv 0 hK
モビルウスの反演の二つの形式は、本では普通は第一種類だけ紹介されています.この問題は第二種類を使っています.f(k)は1<=x<=b、1<=y==dのgcd(x,y)=kの個数F(k)は1<=x<=b、1<=y==dのgcd(x,y)はkの倍数の個数F(k)=(b/k)*(d/k)です.そしてこの問題はf(k)=f (1) 1<=x<=b/k,1<=y<=d/k gcd(x,y)==1
f(1)=sigma(i==min(b,d)u(i)F(i)に変換されます.
もう一つの押し方Sigma(d|n)u(d)=(n=1)もあります.この問題は、Sigma(1<=i==x)Sigma(1<=j==y)(gcd(i,j)=1)=Sigma(1<=i==x)Sigma(1<=j==y)Sigma(d gcd(i,j)u(d)=Sigma(d=Sigma=1=Sigma=1=Sigu=1=Sigma==1=Sigma=Sigma=Sigu=1=Sigma(gma=1=Sigma=Sigma(1=1=Sigma=Sigma===Sigma(1=Sigma=Sigma(1=Sigma=Sigma(1<=i<=x且d|i)Sigma(1<=j==y且d|j)=Sigma(d)*(x/i)*(y/i).

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ms(X) memset(X,0,sizeof(X))
#define mcs(X) memset(X,-1,sizeof(X))
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int mobius[100020];
void getMbs(void)
{
    ms(mobius);
    for(int i=1;i<=100000;i++)
    {
        int target=(i==1?1:0);
        int delta=target-mobius[i];
        mobius[i]=delta;
        for(int j=(i<<1);j<=100000;j+=i)
            mobius[j]+=delta;
    }
}
int main()
{
    int t,ti=0;
    cin>>t;
    getMbs();
    while(++ti<=t)
    {
        int a,b,c,d,k;
        scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
        if(!k) {printf("Case %d: 0
",ti);continue;}
        b/=k,d/=k;
        if(b>d){int tmp=b;b=d;d=tmp;}
        LL res1=0,res2=0;
        for(int i=1;i<=b;i++)
            res1+=(LL)mobius[i]*(b/i)*(d/i);
        for(int i=1;i<=b;i++)
            res2+=(LL)mobius[i]*(b/i)*(b/i);
        printf("Case %d: %I64d
",ti,res1-res2/2);
    }
    return 0;
}