poj 2773 Happy 2006

时间：2021-08-31 15:05:40
// 题意 ：给你两个数 m(10^6),k(10^8) 求第k个和m互质的数是什么
这题主要需要知道这样的结论
gcd(x,n)=1 <==> gcd(x+n,n)=1
证明 假设 gcd(x,n)=1 gcd(x+n,n)!=1
     令 a=n+x b=n 设 gcd（a,b）=k>1
      那么有 a=Ak b=Bk  x+Bk=Ak => x=(A-B)k 
     k是n的因子 那么 x=(A-B)k 显然不成立 因为x不可能含有因子k(因为x,n互质);
    所以假设不成立

那么这题剩下的就算求 比m小 与m互质的数就可以了
#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <math.h>

#include <stdio.h>

#include <string.h>

using namespace std;

#define maxm 100010

#define maxn 1000110

int prim[],p;

bool f[maxn];

int ans[maxn],rp[];

void getprime(){

  int i,j;

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

    prim[i]=;

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

    if(!prim[i])

     for(j=i*i;j<=;j+=i)

        prim[j]=;

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

     if(!prim[i]) prim[p++]=i;//,printf("%d ",i);

}

int main()

{

    getprime();

    int m,k;

    while(scanf("%d %d",&m,&k)!=EOF){

        int i=,j,n=m,num=;

        while(i<p){   //分解

            if(n%prim[i]==){

                rp[num++]=prim[i];

                while(n%prim[i]==) n=n/prim[i];

            }

            if(n==) break;

            i++;

        }

        if(n!=) rp[num++]=n;

        for(i=;i<=m;i++)

            f[i]=;

        for(i=;i<num;i++)//筛选删除

          for(j=rp[i];j<=m;j+=rp[i])

             f[j]=;

        num=;

        for(i=;i<=m;i++) // 其实这里面的num可以用容斥原理算 估计会快在常数上

          if(!f[i]) ans[num++]=i;

        printf("%d\n",ans[(k-)%num]+(k-)/num*m);

    }

    return ;

}

相关文章