hdu1695--GCD（歐拉函數+容斥原理）

hdu1695--GCD（歐拉函數+容斥原理）

GCD Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Appoint description: System Crawler (2015-01-07)

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).
         

題目大意：求1到b內x，1到d內y，gcd(x,y)= k 的對數，二元組無序，要求不重復

x和y的最大公約數都是k，也就是說x，y都是k的倍數，b /= k , d /= k 得到新的區間，需要找到新區間的中互質的對數，要求不重復，所以使大的數為b，小的數為d ，從1到b遍歷-->i，當i小於等於d時，ans加上i的歐拉函數值，當i大於d時，計算1到d中與i互質的個數，累加得到最後的結果。

為防止超時，要將歐拉函數值提前處理好，還有將一個數的分解也要預處理。

#include 
#include 
#include 
using namespace std ;
#define LL __int64
#define maxn 110000
LL euler[maxn] ;//記錄1到i的歐拉函數和
LL p[maxn][30] , p_num[maxn] ; //質因子個數
void sieve()
{
    LL i , j ;
    memset(p_num,0,sizeof(p_num)) ;
    memset(p,0,sizeof(p)) ;
    memset(euler,0,sizeof(euler)) ;
    for(i = 1 ; i < maxn ; i++)
        euler[i] = i ;
    for(i = 2 ; i < maxn ; i++)
    {
        if( euler[i] == i )
        {
            euler[i] = i-1 ;//是=素數
            p[i][p_num[i]++] = i ;
            for(j = 2*i ; j < maxn ; j += i)
            {
                p[j][ p_num[j]++ ] = i ;
                euler[j] = euler[j] * (i-1) / i ;
            }
        }
        euler[i] += euler[i-1] ;
    }
}
int cop(int n,int m)
{
    int i , j , num , temp , x = 1< b ? a : b ;
}
int min(int a,int b)
{
    return a > b ? b : a ;
}
LL f(int a,int b)
{
    int n = max(a,b) , m = min(a,b) ;
    LL num = euler[m] ;
    for(int i = m+1 ; i <= n ; i++)
        num += cop(m,i) ;
    return num ;
}
int main()
{
    int a , b , c , d , k ;
    int t , tt ;
    sieve() ;
    scanf("%d", &t) ;
    for(tt = 1 ; tt <= t ; tt++)
    {
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &k) ;
        if(k == 0 || k > b || k > d)
        {
            printf("Case %d: 0\n", tt);
            continue ;
        }
        printf("Case %d: %I64d\n", tt, f(b/k,d/k) );
    }
    return 0;
}