GCD

2015-08-26 12:08

http://acm.hdu.edu.cn/showproblem.php?pid=1695

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7582    Accepted Submission(s): 2793


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

请忽视注释

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxn 100000
using namespace std;
int phi[100005],fac[1000];
int a,b,c,d,k;
vector<int> x[maxn+5];
bool is[maxn+5];
void get_prim(){
    memset(is, false, sizeof(is));
    for (int i=0; i<maxn; i++) x[i].clear();
    for (int j=2; j<maxn; j+=2) x[j].push_back(2);
    for (int i=3; i<maxn; i+=2)
        if (!is[i]) {
            for (int j=i; j<maxn; j+=i) {
                is[j] = true;
                x[j].push_back(i);
            }
        }
}
void euler(){ //返回euler(n)
    for (int i = 1; i <= maxn; i++) phi[i] = i;
    for (int i = 2; i <= maxn; i += 2) phi[i] /= 2;
    for (int i = 3; i <= maxn; i += 2)
              if(phi[i] == i) {
        for (int j = i; j <= maxn; j += i)
            phi[j] = phi[j] / i * (i - 1);
          }
}
int get_ans(int z){
    int cnt=x[z].size();
    int sum=0;
    for(int num=1;num<(1<<cnt);num++){//cnt个集合,容斥定理中就有2的cnt次方-1项,num是二进制压缩//3为11,代表A1交A2
        int mult=1,ones=0;
        for(int i=0;i<cnt;i++){//i表示第几个集合,例如i=2,表示为100,表示为第三个集合
            if(num&(1<<i)){//当i为0的时候,判断第一个集合是否进行交集操作
                ones++;//当ones为偶数的时候,那么就是减,当noes为奇数的时候为加
                mult*=x[z][i];
            }
        }
        if(ones%2) sum+=b/mult;
        else sum-=b/mult;
    }
    return b-sum;
}
int main()
{
    //freopen("F://in.txt","r",stdin);
    euler();
    get_prim();
    int t;
    scanf("%d",&t);
    for(int Case=1;Case<=t;Case++){
        __int64 ans=0;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(b>d)swap(b,d);
        if(k==0||k>d){
            printf("Case %d: %I64d\n",Case,ans);
            continue;
        }
        b/=k;
        d/=k;
        for(int i=1;i<=b;i++)//printf("%d\n",phi[i]);
        ans+=phi[i];
        //printf("%I64d\n",ans);
        for(int i=b+1;i<=d;i++)
            ans+=get_ans(i);
            printf("Case %d: %I64d\n",Case,ans);
    }
}

AC之路上,我选择坚持~~~

版权声明:本文为博主原创文章,未经博主允许不得转载。