【欧拉函数+容斥原理】HDU 1695 GCD
http://acm.hdu.edu.cn/showproblem.php?pid=1695题意：求和中分别取一个数,问取到的两个数的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;int prime, num; //prime储存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 = e - e / i, prime++] = i; } } for (i = 2; i < L; i++) //递推求和 e += e;}int dfs (int x, int b, int n) //求中有多少个与n非互质{ if (!b) return 0; int ans = 0, i; for (i = x; i < num; i++) ans += b/prime - dfs (i+1, b/prime, 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; //和的gcd为1的对数 for (i = b + 1; i <= d; i++) //求与的互质对数 res += b - dfs (0, b, i); //已经无法用语言形容了，我反正信了 printf ("%I64d\n", res); } return 0; }
页:
[1]