华中科技大学新生赛
Problem - F - Codeforces（取模运算）
题意：一个x如果不能被p整除则结果是x%p，如果可以被整除那么结果是n/p
现在问你n!%p等于多少
题解：
假如n=21,p=7;
我们一个分配率(1%p*2%p*3%p*4%p*5%p......*n%p)
我们发现
结果就是不超过p的一组数字连续相乘
因为7/7==1,14/7==2,不是0
所以结果就是
1*1*2*3*4*5*6%7
2*1*2*3*4*5*6%7
3*1*2*3*4*5*6%7
这个算出来就是最后的结果
所以我们预处理一下1到p-1乘积的前缀
结果就是
imp是快速幂，就是1到p-1的乘积出现的次数就对了
f[n%p]就是多出来那一部分的乘积
imp(f[p-1],n/p)*f[n%p]%p
最后因为在里面没有算能被整除的情况所以，我们递归一下（n/p）就是7%7==1，14%7==2这种情况就可以了
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> //#define double long double #define int long long //#define endl '\n'; using namespace std; const int N=1e6+7,M=1e1; const int INF = 0x3f3f3f3f; const int mod=100003; typedef pair<int,int> PII; int f[N]; int t,p; int imp(int a,int k) { int ans=1; while (k) { if(k&1) ans=ans*a%p; k>>=1; a=a*a%p; } return ans; } int kpl(int x) { if(x<p) return f[x]; int k=imp(f[p-1],x/p)*f[x%p]%p; return k*kpl(x/p)%p; } void solve() { scanf("%lld %lld",&t,&p); int x; f[0]=f[1]=1; for(int i=2;i<p;i++) { f[i]=f[i-1]*i%p; } while (t--) { scanf("%lld",&x); int ans; ans=kpl(x); cout<<ans<<'\n'; } } signed main(){ // std::ios::sync_with_stdio(false); // std::cin.tie(nullptr); int T=1; // cin>>T; while(T--){ solve(); } return 0; }