BZOJ 1101 POI 2007 Zap【モビウス反転】

BZOJ1101 POI2007 Zap
Description
FGDはパスワードを解読しており、与えられた整数a,b,dに対して、x<=a,y<=bを満たし、gcd(x,y)=dを満たす正の整数対x,yがどれだけあるかという類似の質問に答える必要がある.FGDの同級生として、FGDはあなたの助けを望んでいます.
Input
最初の行には、nグループのクエリが合計であることを示す正の整数nが含まれます.(1<=n<=50000)次にn行、各行は1つの問合せを表し、各行は3つの正の整数で、それぞれa,b,dである.(1<=d<=a,b<=50000)
Output
各グループの問い合わせに対して出力ファイルzapに出力.out正の整数で、条件を満たす整数対数を表す.
Sample Input
2 4 5 2 6 4 3
Sample Output
3 2//1組目の質問に対して、条件を満たす整数対は(2,2)、(2,4)、(4,2)である.2組目の質問に対して、条件を満たす整数対は(6,3)、(3,3)である.
セットモビウス
ans=∑ai=1∑bj=1[gcd(i,j)==d] a n s = ∑ i = 1 a ∑ j = 1 b [ g c d ( i , j ) == d ]
dで割ると、⌊ad⌋a d⌋の代わりにa 1 a 1を用い、⌊bd⌋b d⌋の代わりにb 1 b 1を用いて得られる.
ans=∑a1i=1∑b1j=1[gcd(i,j)==1] a n s = ∑ i = 1 a 1 ∑ j = 1 b 1 [ g c d ( i , j ) == 1 ]
[gcd(i,j)==1][gc d(i,j)==1]を交換します.
ans=∑a1i=1∑b1j=1∑p|gcd(i,j)μ(p) a n s = ∑ i = 1 a 1 ∑ j = 1 b 1 ∑ p | g c d ( i , j ) μ ( p )
ans=∑a1i=1∑b1j=1∑p|i,p|jμ(p) a n s = ∑ i = 1 a 1 ∑ j = 1 b 1 ∑ p | i , p | j μ ( p )
Pの列挙を前に挙げます.
ans=∑min(a1,b1)p=1μ(p)⌊a1p⌋⌊b1p⌋ a n s = ∑ p = 1 m i n ( a 1 , b 1 ) μ ( p ) ⌊ a 1 p ⌋ ⌊ b 1 p ⌋
それから処理しますμ μ の接頭辞の和、更に下の関数のブロックに分けて計算します

#include
using namespace std;
#define N 500010
int T,a,b,d,tot=0;
bool mark[N]={0};
int pri[N],mu[N],F[N]={0};
void init(){
    mu[1]=1;
    for(int i=2;iif(!mark[i])pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&pri[j]*i*pri[j]]=1;
            if(i%pri[j]==0){
                mu[i*pri[j]]=0;
                break;
            }else mu[i*pri[j]]=-mu[i];
        }
    }
    for(int i=1;i1]+mu[i];
}
int main(){
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&a,&b,&d);
        a/=d;b/=d;
        int ans=0,up=min(a,b);
        for(int i=1,j;i<=up;i=j+1){
            j=min(a/(a/i),b/(b/i));
            ans+=(F[j]-F[i-1])*(a/i)*(b/i);
        }
        printf("%d
",ans);
    }
    return 0;
}