牛客小白月赛23 B 阶乘

Bertha 。 2023-07-18 02:51 3阅读 0赞

链接:[B 阶乘][B]

题目描述

给定一个正整数 p  
求一个最小的正整数 n，使得 n! 是 p 的倍数

输入描述:  
第一行输入一个正整数T\{T\}T表示测试数据组数  
接下来T行，每行一个正整数p

输出描述:  
输出T行，对于每组测试数据输出满足条件的最小的n

示例1

输入

4  
1  
2  
4  
8

输出

1  
2  
4  
4

备注:  
T≤10^ 3,p≤10^9

题解：  
计算n！%p=0  
等价于（1 \* 2 \* 3 \* 4 \* 5 \* … \* n）%p=0 ，如果满足前n个数中有若干个数乘积sum%p=0，若干个数的最大的那个就是答案。

这些数怎么求，  
①一个数是素数肯定答案就是它本身。  
②我们从1开始累乘，  
若累乘结果可以%p=0，则输出答案。  
若p%i==0&&p / i > i ,如果p/i是个素数，则这个素数就是答案。因为一个数分成两个数乘积，较大的一个因数是素数，它不可拆，较小的一个因数不论能不能拆，与结果无关，则这个素数就是最终答案。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    void io(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
    ll judge(ll x)
    { 
    	for(int i=2;i*i<=x;i++)
    	{ 
    		if(x%i==0)
    			return 1;
    	}
    	return 0;
    }
    int main()
    { 
    	io();
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		ll p;
    		cin>>p;
    		ll sum=1,k;
    		for(int i=1;;i++)
    		{ 
    			sum=(sum*i)%p;
    			if(sum==0)//乘积为p的倍数，即答案
    			{ 
    				k=i;
    				cout<<k<<endl;
    				break;
    			}
    			if(p%i==0&&p/i>i&&!judge(p/i))//若为素数，不可分解，即答案
    			{ 
                    		cout<<p/i<<endl;
                    		break;
    			}
    		}
    		
    	}
    	return 0;
    }

[B]: https://ac.nowcoder.com/acm/contest/4784/B