hdoj 1695 GCD【反発原理+Euler関数】【2つの区間の中のすべての重複しない質量のペアを求めます】

GCD
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7013    Accepted Submission(s): 2580
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). 
    
    
    
    
     
   
   
   
   

 
标题:二つの区間[a,b]と[c,d]を与えて、何個の数対(x,y)【xは区間[a,b]に属するかを求めさせる   yは区間[c,d]に属し、(x,y)  および(y,x)は、gcd(x,y)==kを満たす数対を計算する.
解析:変換区間n=b/k,m=d/k.問題は区間[1,n]と[1,m]の中のすべての重複しない質量対(x,y)【xは[1,n]に属し、yは[1,m]】に属する.
実装:nを仮定してみましょう  <= mは、xが区間[1,n]に属し、yが区間[1,n]に属する2つの状況に分けて解く必要がある.2,xは区間[1,n]に属し,yは区間[n+1,m]に属する.
ケース1:xが区間[1,n]に属するものとyが区間[1,n]に属するもののすべての重複しない素数対(x,y)の数はn個数のEuler関数の和である.
どうして?xから見ると,数対(x,y)と(y,x)は同一の数対であるため,xケース2:反発原理は、言うまでもなく、y(n+1<=y<=m)ごとに列挙し、区間[1,n]の中で現在のyと互質する個数を求め、累積すればよい.
 
コード:
 

#include <cstdio>
#include <cstring>
#include <cmath>
#define LL long long
#define MAX 100000+10
using namespace std;
LL eu[MAX];//eu[i]    [1  i ]              
int p[100], q;//       
void euler()
{
	int i, j;
	eu[1] = 1;
	for(i = 2; i < MAX; i++)
	{
		if(!eu[i])
		{
			for(j = i; j < MAX; j += i)
			{
				if(!eu[j]) eu[j] = j;
				eu[j] = eu[j] * (i-1) / i;
			}
		}
		eu[i] += eu[i-1];
	}
} 
void getp(int n)// n     
{
	int i;
	q = 0;
	for(i = 2; i*i <= n; ++i)
	{
		if(n % i == 0)
		{
			p[q++] = i;
			while(n % i == 0)
			n /= i;
		}
	}
	if(n > 1) p[q++] = n;
} 
int nop(int m)//  1 m      n         
{
	int top = 0;
	int i, j, t;
	int que[100000];
	que[top++] = -1;
	for(i = 0; i < q; i++)
	{
		t = top;
		for(j = 0; j < t; ++j)
		{
			que[top++] = que[j] * p[i] * (-1);
		}
	}
	int sum = 0;
	for(i = 1; i < top; i++)
	sum += m/que[i];
	return sum;
}
int main()
{
	int t;
	int i, j = 1;
	int a, b, c, d, k;
	int n, m; 
	euler(); 
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
		if(k == 0)
		{
			printf("Case %d: 0
", j++);
			continue;
		}
		n = b / k;
		m = d / k;
		if(n > m)//n   m   
		{
			a = n;
			n = m;
			m = a;
		}
		LL ans = eu[n];//  [1-n]            
		for(i = n+1; i <= m; i++)
		{
			getp(i);// i    
			ans += n-nop(n);//   [1-n]          i    
		}
		printf("Case %d: %lld
", j++, ans);
	}
	return 0;
}