HDU1695 GCD [容斥]

$GCD$GCD

$Description$Description
$给出n、m、k，求出1\&lt;=x\&lt;=n,1\&lt;=y\&lt;=m且gcd(x,y)==k的（x,y）的对数$给出n、m、k，求出1<=x<=n,1<=y<=m且gcd(x,y)==k的（x,y）的对数.

$n,m,k\&lt;=10^5$n,m,k<=105

$最初想法$最初想法
按照 能量采集 的方法.
时间复杂度 $O\left(NlogN\right)$O(NlogN)

#include<cstdio>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 100005;

int Test_cnt;
int T;
int N;
int M;
int K;
int cnt[maxn];

void Work(){
        int a, c;
        scanf("%d%d%d%d%d", &a, &N, &c, &M, &K);
        if(!K || K > N || K > M){ printf("0\n"); return ; }
        int Lim = std::min(N, M);
        for(reg int d = Lim; d >= K; d --){
                cnt[d] = (N/d) * (M/d);
                for(reg int i = 2; i*d <= Lim; i ++) cnt[d] -= cnt[i*d];
        }
        printf("Case %d: %d\n", ++ Test_cnt, cnt[K]);
}

int main(){
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}

$正解部分$正解部分
然而上面的方法连样例都过不去 , 为什么呢?
假设 $N\&lt;M$N<M, 因为在 $N$N 与 $M$M 的重合部分会有重复计算,
所以要减去这些重复的计算, 再计算一次 $N$N与 $N$N 之间的答案, 除 $2$2后与 $N$N和 $M$M得出的答案作差即可.

时间复杂度同上 .

$实现部分$实现部分
没什么好说的 .

#include<cstdio>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 200005;

int Test_cnt;
int T;
ll N;
ll M;
ll K;
ll cnt[maxn];

void Work(){
        ll a, c;
        scanf("%lld%lld%lld%lld%lld", &a, &N, &c, &M, &K);
        if(K > N || K > M){ printf("Case %d: 0\n", ++ Test_cnt); return ; }
        ll Lim = std::min(N, M);
        for(reg ll d = Lim; d >= 1; d --){
                cnt[d] = (N/d) * (M/d);
                for(reg ll i = 2; i*d <= Lim; i ++) cnt[d] -= cnt[i*d];
        }
        ll Ans = cnt[K];
        for(reg ll d = Lim; d >= 1; d --){
                cnt[d] = (Lim/d) * (Lim/d);
                for(reg ll i = 2; i*d <= Lim; i ++) cnt[d] -= cnt[i*d];
        }
        printf("Case %d: %lld\n", ++ Test_cnt, Ans-(cnt[K]>>1));
}

int main(){
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}