2022寒假训练 数论 L - Happy 2006

POJ 2773 Happy 2006【GCD/欧拉函数】

题意

输入m和k，寻找与m互质的第k个数

前置知识

gcd(a+b*k,b)=gcd(a,b)
证明：https://www.zhihu.com/question/386209132

思路

我们用类似埃筛的手法筛出[1，m-1]内的与m互质的数，因为最大公约数会循环，所以当k大于m时，只需选出循环的数 加上 k/phi（x）* m
这里埃筛又有坑
如果我们按板子来
在j=ii这里出现问题
因为在埃筛的情况下，已经默认某些数是质数，而我们这里 是 1_{m-1中的某个数与m互质，以致在（1}i-1）i 这范围中少筛了一些数！

//引自 oiwiki
// C++ Version
int Eratosthenes(int n) {
  int p = 0;
  for (int i = 0; i <= n; ++i) is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;  // prime[p]是i,后置自增运算代表当前素数数量
      if ((long long)i * i <= n)
        for (int j = i * i; j <= n; j += i)
          // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
          // 的倍数开始，提高了运行速度
          is_prime[j] = 0;  // 是i的倍数的均不是素数
    }
  }
  return p;
}

所以我们改成最普通的 ,并且这里的n可以优化 ，每出现一个非互质的数，当成因数，除掉，缩小筛选因数的范围。

这里输出 又有个坑，要采用约瑟夫循环:
eg：2006 有 928 个 互质的数
当k=928 时 k%928=0 但我们应该取的是928 ，所以 (k-1)%928+1
同理 对于 k/phi(m)m [1,928] 是 k=0 但928 代入算出 0 ，所以 我们使式子化为 （k-1）/phi（x） m

代码

#include
#include
using namespace std;
#define int long long
#define ll long long
const int N=1e6+5;
bool is_ys[N]={0};
int yi[N];
int cnt,pr[N];
int gcd(int a,int b){
    if(!b)    return a;
    return gcd(b,a%b);
}

signed main()
{
	ll m,k;
	while(cin>>m)
	{
		memset(is_ys,0,sizeof(is_ys));
		memset(yi,0,sizeof(yi));
		cin>>k;
		int p=m;
		for(int i=2;i<=p;i++)
		{
			if(m%i==0&&!is_ys[i])
			{
				p=p/i;
				is_ys[i]=true;
				for(int j=1;j*i<=m;j++)
				{
					is_ys[j*i]=true;
				}
			}
		}
		int index=0;
		for(int i=1;i<=m;i++)
		{
			if(!is_ys[i])
			{
				yi[++index]=i;
			}
		}
		cout<