首页 > ACM题库 > HDU-杭电 > HDU 1695 GCD-数论-[解题报告] C++
2013
12-21

HDU 1695 GCD-数论-[解题报告] C++

GCD

问题描述 :

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.

输入:

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.

输出:

For each test case, print the number of choices. Use the format in the example.

样例输入:

2
1 3 1 5 1
1 11014 1 14409 9

样例输出:

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,2,...,b/k]  第二个区间:[b/k+1,b/k+2,...,d/k]
读第一个区间我们只要利用欧拉函数雷家没个数的质因数的个数即可,第二个区间我们任取x,
要求[1,2,...,b/k]中所有与x互质的数的个数,这里我们用到容斥原理:先将x质因数分解,
求得[1,2,...,b/k] 里所有能被x的质因数整除的数的个数,然后用b/k减去即可。 
*/ 
#include<iostream>
#include<string.h>
#define size 100010
using namespace std;
struct Num
{
   int count;
   int prime[20];
}N[size];
__int64 elur[size];

void Elur()
{
    elur[1]=1;
    for(int i=0;i<size;i++) N[i].count=0;
    for(int i=2;i<size;i++)
    {
        if(!elur[i])    //首先求素数 
        {
            for(int j=i;j<size;j+=i)
            {
                if(!elur[j]) elur[j]=j;
                elur[j]=elur[j]*(i-1)/i; //欧拉函数公式 
                N[j].prime[N[j].count]=i;
                N[j].count++;
            }
        }
        elur[i]+=elur[i-1];  //elur[i]表示前i个数的质因数的累加。
    }  
}

__int64 Inclusion_exclusion(int index , int b , int n)
{  //index表示此刻算到哪个质因数,b表示在1~b中计算被质因数整除的个数,指第二个区间的哪一个数。 
    __int64 r=0 , t;
    for(int i=index;i<N[n].count;i++)  //x与y的最大公约数为k*p(p为质数) 
    {
        t=b/N[n].prime[i];  
        r+=t-Inclusion_exclusion(i+1,t , n);  //因为防止有数被重复计算,所以根据容斥定理 
    }
    return r;
} 
int main()
{
    int a , b, c, d , k;
    int t ,tt=0;
    Elur();
    __int64 ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0)
        {
            printf("Case %d: 0\n",++tt);
            continue;
        }
        if(b>d)
        {
           b^=d;
           d^=b;
           b^=d;
        }
        b=b/k;
        d=d/k;
        ans=elur[b];
        for(int i=b+1;i<=d;i++)
        {
            ans+=b-Inclusion_exclusion(0,b,i);
        } 
        printf("Case %d: %I64d\n",++tt,ans);
    } 
    return 0;
}

解题报告转自:http://blog.csdn.net/liwen_7/article/details/8048436


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!