HDU 1695 GCD(オイラー関数+反発原理)

GCD
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4272    Accepted Submission(s): 1492
Problem Description
Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.
Yoiu can assume that a = c = 1 in all test cases.
 
 
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
 
 
Output
For each test case, print the number of choices. Use the format in the example.
 
 
Sample Input
2 1 3 1 5 1 1 11014 1 14409 9
 
 
Sample Output
Case 1: 9 Case 2: 736427
Hint
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).
 
 
Source
2008 “Sunline Cup” National Invitational Contest
 
 
Recommend
wangye
 
 
 
标题:1~a,1~bの中から(x,y)がgcd(x,y)=kを満たすことを選び、(x,y)の対数を求め、a,b<=10^5
考え方:gcd(x,y)==kはx,yがkで除去できることを示しているが,kで除去できるものは必ずしもgcd=kではない , 満たさなければならない
互質関係.問題は1~a/kと1~b/k間の互質対数を求める問題に転化する
aを小さい数に設定すれば、y>xで一意性を保つことができる(テーマ要求、例えば[1,3]=[3,1])
次の2つのケース:
1.y<=aでは対数は1~aのEuler関数の積算和(考えやすい)である.
2.y>=a、この時点でオラ関数が使えなくなりましたが、どうすればいいですか?反発原理を用いてyと1~aの相互対数問題を
 

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013/8/19 22:08:43
  4 File Name     :F:\2013ACM  \    \  \HDU\HDU1695GCD.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 
 21 const int MAXN = 10000;
 22 int prime[MAXN+1];
 23 void getPrime()
 24 {
 25     memset(prime,0,sizeof(prime));
 26     for(int i = 2;i <= MAXN;i++)
 27     {
 28         if(!prime[i])prime[++prime[0]] = i;
 29         for(int j = 1;j <= prime[0] && prime[j] <= MAXN/i;j++)
 30         {
 31             prime[prime[j]*i] = 1;
 32             if(i%prime[j] == 0)break;
 33         }
 34     }
 35 }
 36 long long factor[100][2];
 37 int fatCnt;
 38 int getFactors(long long x)
 39 {
 40     fatCnt = 0;
 41     long long tmp = x;
 42     for(int i = 1; prime[i] <= tmp/prime[i];i++)
 43     {
 44         factor[fatCnt][1] = 0;
 45         if(tmp%prime[i] == 0)
 46         {
 47             factor[fatCnt][0] = prime[i];
 48             while(tmp%prime[i] == 0)
 49             {
 50                 factor[fatCnt][1]++;
 51                 tmp /= prime[i];
 52             }
 53             fatCnt++;
 54         }
 55     }
 56     if(tmp != 1)
 57     {
 58         factor[fatCnt][0] = tmp;
 59         factor[fatCnt++][1] = 1;
 60     }
 61     return fatCnt;
 62 }
 63 int euler[100010];
 64 void getEuler()
 65 {
 66     memset(euler,0,sizeof(euler));
 67     euler[1] = 1;
 68     for(int i = 2;i <= 100000;i++)
 69         if(!euler[i])
 70             for(int j = i; j <= 100000;j += i)
 71             {
 72                 if(!euler[j])
 73                     euler[j] = j;
 74                 euler[j] = euler[j]/i*(i-1);
 75             }
 76 }
 77 int calc(int n,int m)//n < m, 1-n  m       
 78 {
 79     getFactors(m);
 80     int ans = 0;
 81     for(int i = 1;i < (1<<fatCnt);i++)
 82     {
 83         int cnt = 0;
 84         int tmp = 1;
 85         for(int j = 0;j < fatCnt;j++)
 86             if(i&(1<<j))
 87             {
 88                 cnt++;
 89                 tmp *= factor[j][0];
 90             }
 91         if(cnt&1)ans += n/tmp;
 92         else ans -= n/tmp;
 93     }
 94     return n - ans;
 95 }
 96 int main()
 97 {
 98     //freopen("in.txt","r",stdin);
 99     //freopen("out.txt","w",stdout);
100     getPrime();
101     int a,b,c,d;
102     int T;
103     int k;
104     scanf("%d",&T);
105     int iCase = 0;
106     getEuler();
107     while(T--)
108     {
109         iCase++;
110         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
111         if(k == 0 || k > b || k > d)
112         {
113             printf("Case %d: 0
",iCase);
114             continue;
115         }
116         if(b > d)swap(b,d);
117         b /= k;
118         d /= k;
119         long long ans = 0;
120         for(int i = 1;i <= b;i++)
121             ans += euler[i];
122         for(int i = b+1;i <= d;i++)
123             ans += calc(b,i);
124         printf("Case %d: %I64d
",iCase,ans);
125     }
126     
127     return 0;
128 }