首页 > 代码库 > hdu1695--GCD（欧拉函数+容斥原理）

hdu1695--GCD（欧拉函数+容斥原理）

2024-10-29 08:21:39   206人阅读

GCD
Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status
Appoint description: 

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 <cstdio>
#include <cstring>
#include <algorithm>
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<<p_num[m] ;
    int ans = 0 ;
    for(i = 1 ; i < x ; i++)
    {
        for(j = 0 , num = 0 , temp = 1 ; j < p_num[m] ; j++)
        {
            if( (1<<j) & i )
            {
                num++ ;
                temp *= p[m][j] ;
            }
        }
        if( num % 2 )
            ans += n/temp ;
        else
            ans -= n/temp ;
    }
    return n-ans ;
}
int max(int a,int b)
{
    return a > 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;
}


hdu1695--GCD（欧拉函数+容斥原理）


联系
我们