C - Co-prime

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.

·······

这道题分几步：

1、先把n用算术基本原理拆分成不同的质数，如果a~b中的数是这些质数的倍数那其肯定不与n互质，a~b的总个数减去不与n互质的数剩下来就是与n互质的数啦。

2、先计算1~a-1中与n互质的个数，再计算1~b中与n互质的个数，相减。

#include<iostream>

using namespace std;

typedef long long ll;

ll a[];

int main()

{

    ll t;

    cin>>t;

    for(ll ii=;ii<=t;ii++)

    {

        ll x,y,n;

        cin>>x>>y>>n;

        ll num=,sum=,all=,times;

        for(int i=;i*i<=n;i++)   //向a数组里塞n的质因数

        {

             if(n%i==)

            {

                num++;

                a[num]=i;

            }

            while(n%i==)

            {

                n=n/i;

            }

         }

        if(n>)  a[++num]=n;

        for(int i=;i<(<<num);i++)

        {

            times=,sum=;

            for(int j=;j<num;j++)  //num个因数,乘了几个

            {

                if(&(i>>j))      //判断有没有选中第j个因数

                {

                    sum*=a[j+];

                    times++;

                }

            }

            if(sum==||sum==)

            continue;

            if(times%==)

            {

                all+=y/sum;

                all-=(x-)/sum;

            }

            else{

                all-=y/sum;

                all+=(x-)/sum;

            }

        }

        printf("Case #%lld: %lld\n",ii,y-x+-all);

    }

    return ;

}

以上。

巴特西

C - Co-prime

最新文章

热门文章