HDU 1695 GCD【莫比乌斯反演】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1695

题意：

1≤x≤m,1≤y≤n ，求 gcd(x,y)=k 的 (x,y) 的对数。

分析：

首先根据莫比乌斯反演我们有
F(n)=∑n|df(d)⇒f(n)=∑n|dμ(d/n)F(d)
设
f(d)： 满足 gcd(x,y)=d 且 x,y 均在给定范围内的 (x,y) 的对数。
F(d)： 满足 d|gcd(x,y) 且 x,y 均在给定范围内的 (x,y) 的对数。
显然 F(x)=[n/x]∗[m/x] ，反演后我们得到 f(x)=∑x|dμ(d/x)[n/d]∗[m/d]
那么这样所求即为f(k)
我们将 x/=k,y/=k,n/=k,m/=k ，即 gcd(x,y)=1 ，这样就可以将问题转化为求解 f(1) 了 f(1)=∑i=1min(n,m)μ(i)[n/i][m/i]
我们再利用 [n/i] 是一个分段函数的特性，并预处理出 μ 函数的前缀和进行分段优化。
最后记得进行去重。

代码：

/*
-- Hdu 1695
-- Create by jiangyuzhu
-- 2016/5/29
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
#define sa(n) scanf("%d", &(n))
#define sal(n) scanf("%I64d", &(n))
#define pl(x) cout << #x << " " << x << endl
#define mdzz cout<<"mdzz"<<endl;
const int maxn = 1e5 + 5 ;
int tot = 0;
int miu[maxn], prime[maxn], f[maxn];
bool flag[maxn];
void mobius()
{
    miu[1] = 1;
    tot = 0;
for(int i = 2; i < maxn; i++){
if(!flag[i]){
            prime[tot++] = i;
            miu[i] = -1;
        }
for(int j = 0; j < tot && i * prime[j] < maxn; j++){
            flag[i * prime[j]] = true;
if(i % prime[j]) miu[i * prime[j]] = -miu[i];
else{
                miu[i * prime[j]] = 0;
break;
            }
        }
    }
    f[0] = 0;
for(int i = 1; i < maxn; i++) f[i] = f[i - 1] + miu[i];
}
int main (void)
{
    mobius();
int T;sa(T);
int a, b, c, d, k;
for(int kas = 1; kas <= T; kas++){
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
if(k == 0){
printf("Case %d: 0\n", kas);
continue;
        }
        b /= k;
        d /= k;
if(b > d) swap(b, d);
        ll ans = 0, anss = 0;
int n;
for(int i = 1; i <= b; i = n + 1){
            n = min(b / (b / i), d / (d / i));
            ans += (f[n] - f[i - 1]) * 1ll * (b / i) * (d / i);
        }
for(int i = 1; i <= b; i = n + 1){
            n = b / (b / i);
            anss += (f[n] - f[i - 1]) * 1ll * (b / i) * (b / i);
        }
        ans -= anss / 2;
printf("Case %d: %I64d\n", kas, ans);
    }
return 0;
}