phi

给定 \(T\) 个正整数 \(n\) ,对于每个 \(n\) ，输出做小的 \(m\) ,使得 \(\phi (m)\ge n\).

思路1：搞个线性欧拉函数筛，后缀最大值，二分查找

思路2：直接求最小比 \(n\) 大的质数

思路2的code

#include<bits/stdc++.h>

using namespace std;

const int N=1000006;

int prime[N],tot;

bool vis[N];

void init()

{

	for(int i=2;i<N;++i)

	{

		if(!vis[i])

		{

			prime[++tot]=i;

		}

		for(int j=1;j<=tot;++j)

		{

			if(i*prime[j]>N)break;

			vis[i*prime[j]]=1;

		}

	}

}

int T,n;

int main()

{

	init();

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		if(n==1)puts("1");

		else printf("%d\n",prime[upper_bound(prime+1,prime+tot+1,n)-prime]);

	}

	return 0;

}

巴特西

phi

最新文章

热门文章