首页 > 代码库 > Co-prime

Co-prime

2024-09-02 15:20:12   220人阅读

Co-prime

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

 

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 <= 1015) and (1 <=N <= 109).
 
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
21 10 23 15 5
 
Sample Output
Case #1: 5Case #2: 10
Hint
In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.
分析：求出n的素因子，然后容斥求解出不互质的个数，剩下的就是互质的个数；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")const int maxn=1e5+10;using namespace std;inline ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}inline ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline void umax(ll &p,ll q){if(p<q)p=q;}inline void umin(ll &p,ll q){if(p>q)p=q;}inline ll read(){    ll x=0;int f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int n,m,k,t,cnt,fac[maxn],cas;ll x,y;void init(int x){    cnt=0;    if(x%2==0){        fac[++cnt]=2;        while(x%2==0)x/=2;    }    for(int i=3;(ll)i*i<=x;i+=2)    {        if(x%i==0)        {            fac[++cnt]=i;            while(x%i==0)x/=i;        }    }    if(x>1)fac[++cnt]=x;}ll gao(ll x){    ll ret=0;    for(int i=1;i<(1<<cnt);i++)    {        ll num=0,now=1;        for(int j=0;j<cnt;j++)        {            if(i&(1<<j))            {                ++num;                now*=fac[j+1];            }        }        if(num&1)ret+=x/now;        else ret-=x/now;    }    return x-ret;}int main(){    int i,j;    scanf("%d",&t);    while(t--)    {        scanf("%lld%lld%d",&x,&y,&n);        init(n);        printf("Case #%d: %lld\n",++cas,gao(y)-gao(x-1));    }    return 0;}
 

Co-prime


联系
我们