Co-prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4090 Accepted Submission(s): 1619

Problem Description

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10¹⁵) and (1 <=N <= 10⁹).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

1 10 2

3 15 5

Sample Output

Case #1: 5

Case #2: 10

思路：求1~m中与n互素的数的个数。

#include <cstdio>

#include <vector>

using namespace std;

typedef long long LL;

LL sieve(LL m,LL n)

{

    vector<LL> divisor;

    for(LL i=;i*i<=n;i++)

    {

        if(n%i==)

        {

            divisor.push_back(i);

            while(n%i==)    n/=i;

        }

    }

    if(n>)    divisor.push_back(n);

    LL ans=;

    for(LL mark=;mark<(<<divisor.size());mark++)

    {

        LL odd=;

        LL mul=;

        for(LL i=;i<divisor.size();i++)

        {

            if(mark&(<<i))

            {

                mul*=divisor[i];

                odd++;

            }

        }

        LL cnt=m/mul;

        if(odd&)    ans+=cnt;

        else ans-=cnt;

    }

    return m-ans;

}

LL a,b,n;

int main()

{

    int T;

    scanf("%d",&T);

    for(int cas=;cas<=T;cas++)

    {

        scanf("%lld%lld%lld",&a,&b,&n);

        LL res=sieve(b,n)-sieve(a-,n);

        printf("Case #%d: ",cas);

        printf("%lld\n",res);

    }

    return ;

}

巴特西

HDU4135(容斥原理)

Co-prime

最新文章

热门文章