2022寒假牛客第一场-牛牛数论

牛牛数论

D-牛牛做数论_2022牛客寒假算法基础集训营1 (nowcoder.com)

用到欧拉函数的定义

第一问 即最多质数相乘

第二问 只有质数的时候得到p-1/p 由于 当p不是质数时，会导致个数不是p-1个 所以 p-1/p > p-1/p+1

所以 我们可以得到 答案。

#include
using namespace std;
using ll = long long;
#define int long long
int prime[1100];
bool is_prime[1100];
int inx;
void shai()
{
    is_prime[0]=is_prime[1]=0;
    for(int i=2;i<1100;i++)
    {
        if(!is_prime[i])
        {
            is_prime[i]=1;
            prime[++inx]=i;
            for(int j=i*i;j<1100;j+=i)
            {
                is_prime[j]=1;
            }
        }    
    }
}
void solve()
{
    ll n;
    cin>>n;
    if(n==1)
    {
    	cout<<-1<n)
    	{
    		ans=ans/prime[i];
    		break;
		}
	}
	cout<=2;i--)
    {
    	flag=1;
    	for(int k=2;k*k<=i;k++)
    	{
    		if(i%k==0)
    		{
    			flag=0;
                break;
			}
		}
		if(flag==1)
		{
 //           cout<<"ok"<<" ";
			cout<>t;
    while(t--)
    {
        solve();
    }
}