http://acm.hdu.edu.cn/showproblem.php
pid=1695
非常经典的题。同一时候感觉也非常难。
在区间 [a,b] 和[c,d]内分别随意取出一个数 x,y, 使得 gcd(x,y) = k。问这种 (x,y) 有多少对。能够觉得 a,c 均为 1,并且 gcd(5,7)与 gcd(7,5)是同一种。
由于 gcd(x,y) = k,那么 gcd(x/k,y/k) = 1。也就是求区间 [1,b/k] 和[1,d/k]内这种 (x,y) 对使得 gcd(x,y) = 1。
为了防止计数反复,首先假定 b/k <= d/k,那么当 y <= b/k 时。这种对数有 Euler[y]个。当 y > b/k 时,先把 y 进行素因子分解为 p1,p2...pi。仅仅要可以求出 [1,b/k] 内与 y 不互质的数,那么与 y 互质的数用 b 减去就行了。求与 y 不互质的数的个数用到容斥原理。由于某些素因子的倍数是一样的,令 pi 的整数倍集合为 Ai, 那么就是求这些集合的并。
求集合的并依据容斥关系进行 dfs。
这个想了好久没有想出来,參考了某大神的博客写出来的。大体思路就是如果素因子分解出来是 p1,p2,p3,先把仅仅有 p1 倍数的个数求出来。这是一个递归的过程。即是 p1 倍数的个数减去 p1p2 倍数的个数减去 p1p2p3 倍数的个数,相同的对于 p2,p2 倍数的个数减去 p2p3 倍数的个数。
- #include <stdio.h>
- #include <iostream>
- #include <map>
- #include <set>
- #include <list>
- #include <stack>
- #include <vector>
- #include <math.h>
- #include <string.h>
- #include <queue>
- #include <string>
- #include <stdlib.h>
- #include <algorithm>
- //#define LL long long
- #define LL __int64
- #define eps 1e-12
- #define PI acos(-1.0)
- #define C 240
- #define S 20
- using namespace std;
- const int maxn = 100010;
- int flag[maxn];
- int prime[maxn];
- int phi[maxn];
- vector <int> edge[maxn];
- int test,a,b,c,d,k;
- //基于素数筛的欧拉函数
- void init()
- {
- memset(flag,0,sizeof(flag));
- prime[0] = 0;
- phi[1] = 1;
- for(int i = 2; i < maxn; i++)
- {
- if(flag[i] == 0)
- {
- prime[++prime[0]] = i;
- phi[i] = i-1;
- }
- for(int j = 1; j <= prime[0] && prime[j]*i < maxn; j++)
- {
- flag[prime[j]*i] = 1;
- if(i % prime[j] == 0)
- phi[prime[j]*i] = phi[i]*prime[j];
- else phi[prime[j]*i] = phi[i]*(prime[j]-1);
- }
- }
- }
- //vector存每一个数的素因子。
- void spilt()
- {
- for(int i = 1; i < maxn; i++)
- {
- int tmp = i;
- for(int j = 1; prime[j]*prime[j] <= tmp; j++)
- {
- if(tmp % prime[j] == 0)
- {
- edge[i].push_back(prime[j]);
- while(tmp % prime[j] == 0)
- tmp /= prime[j];
- }
- if(tmp == 1)
- break;
- }
- if(tmp > 1)
- edge[i].push_back(tmp);
- }
- }
- //求小于等于b的与cur不互质的数的个数
- LL dfs(int st, int b, int cur)
- {
- LL res = 0;
- for(int i = st; i < (int)edge[cur].size(); i++)
- {
- int k = b/edge[cur][i];
- res += k - dfs(i+1,k,cur);
- }
- return res;
- }
- int main()
- {
- init();
- spilt();
- scanf("%d",&test);
- for(int item = 1; item <= test; item++)
- {
- scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
- if(k == 0 || k > b || k > d)
- {
- printf("Case %d: 0\n",item);
- continue;
- }
- b /= k;
- d /= k;
- if(b > d)
- swap(b,d);
- LL ans = 0;
- for(int i = 1; i <= b; i++)
- {
- ans += phi[i];
- }
- for(int i = b+1; i <= d; i++)
- {
- ans += b-dfs(0,b,i);
- }
- printf("Case %d: %I64d\n",item,ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2133237.html