【欧拉函数+容斥原理】HDU 1695 GCD

基德KID.1412

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

题意：求[a,b]和[c,d]中分别取一个数,问取到的两个数的gcd=k的对数！！其中(2,3)跟(3,2)这2种类型只算一种，视为重复

Sample Input
2
1 3 1 5 1
1 11014 1 14409 9

Sample Output
Case 1: 9
Case 2: 736427

#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define eps 1e-8#define PI 3.14159265358979#define inf 0x3fffffff#define L 100005long long e[L];int prime[L][20], num[L];    //prime[j]储存i的第j个质因子，num储存i的质因子个数void Euler (){    int i, j;    for (i = 1; i < L; i++)    //初始化        e = i;    for (i = 2; i < L; i++)    {        if (e == i)    //只有素数才可进来        {            e = i - 1;            for (j = i << 1; j < L; j += i)    //求欧拉的同时求质因子                e[j] = e[j] - e[j] / i, prime[j][num[j]++] = i;        }    }    for (i = 2; i < L; i++)    //递推求和        e += e[i-1];}int dfs (int x, int b, int n)    //求[1,b]中有多少个与n非互质{    if (!b)        return 0;    int ans = 0, i;    for (i = x; i < num[n]; i++)        ans += b/prime[n] - dfs (i+1, b/prime[n], n);    //容斥原理    return ans;}int main(){    int t, a, b, c, d, k, cc = 1, i;    long long res;    memset (num, 0, sizeof(num));    Euler ();    scanf ("%d", &t);    while (t--)    {        scanf ("%d%d%d%d%d", &a, &b, &c, &d, &k);        printf ("Case %d: ", cc++);        if (!k)    //k==0下面作为分母会出大错        {            puts ("0");            continue;        }        b /= k, d /= k;    //问题的转化，转化成求gcd=1的对数        if (d < b)            d ^= b, b ^= d, d ^= b;        res = e;    //[1,b]和[1,b]的gcd为1的对数        for (i = b + 1; i <= d; i++)    //求[b+1,d]与[1,b]的互质对数            res += b - dfs (0, b, i);    //已经无法用语言形容了，我反正信了        printf ("%I64d\n", res);    }    return 0;   }