外贸网站seo推广方案/搜一搜百度

E

题意：
就是给你一个数组，一个x和y，然后z就是数组中每个元素阶乘的相乘，然后问你x的多少次方*z是y的阶乘的因子，尽量让次方大，输出答案。同时呢va[1]+va[2]…+va[n]<y。

思考：
你看题目说的，尽量让x的次方大，而且那个条件就隐含地告诉你了，z是y的因子，所以x的次方至少也是0。现在呢就是找x的最高次方，其实呢这种题无外乎就是找质因子，对x找出质因子，比如其中一个是p，出现了b次，假如y!中出现了c次把，z中出现了a次。你说说，x的次方最多是多少，既然要满足是y!的因子，那么对于每个质因子出现的次数都必须小于y！中出现的次数，所以对于因子p，次方最大为(c-a)/b。所以对每个因子的最大出现次数去min就是答案了。
还用到了一个定理就是，一个数n的阶乘中，质因子x的次数为一个公式代码中的cal。
Q.solve中处理一个大数分解成多个质数的多少次幂时，不能处理1。
然后有时候Q里面要用unsigned long long

代码：

int T,n,m,k;
int va[N];struct BigIntegerFactor{const static int maxm = 1e6+16;LL prime[maxm],p[maxm],fac[maxm],sz,cnt;inline LL mul(LL a,LL b,LL mod){int sum = (a*b-(ll)((long double)a*b/mod)*mod+mod)%mod;return sum%mod;/*如果mod过大，可能爆ll，所以用慢速乘int sum = 0;while(b){if(b&1) sum = (sum+a)%mod;a <<= 1;a %= mod;b >>= 1;}return sum%mod;当然也可以用O(1)的快速乘int sum = (a*b-(ll)((long double)a*b/mod)*mod+mod)%mod;return sum%mod;*/}void init(int maxn){int tot = 0; sz = maxn-1;for(int i = 1;i <= sz; ++i) p[i] = i;for(int i = 2;i <= sz; ++i){if(p[i] == i) prime[tot++] = i;for(int j = 0;j<tot&&1ll*i*prime[j]<=sz; ++j){p[i*prime[j]] = prime[j];if(i%prime[j] == 0) break;}}}LL powl(LL a,LL x,LL mod){LL res = 1LL;while(x){if(x&1) res = mul(res,a,mod);a = mul(a,a,mod);x >>= 1;}return res;}bool check(LL a,LL n){LL t = 0,u = n-1;while(!(u&1)) t++,u >>= 1;LL x = powl(a,u,n),xx = 0;while(t--){xx = mul(x,x,n);if(xx==1 && x!=1 && x!=n-1) return false;x = xx;}return xx == 1;}bool miller(LL n,int k){if(n == 2) return true;if(n < 2 || !(n&1)) return false;if(n <= sz) return p[n] == n;for(int i = 0;i <= k; ++i){if(!check(rand()%(n-1)+1,n)) return false;}return true;}inline LL gcd(LL a,LL b){return b == 0 ? a : gcd(b,a%b);}inline LL Abs(LL x){return x < 0 ? -x : x;}LL Pollard_rho(LL n){LL s = 0,t = 0,c = rand()%(n-1)+1,v = 1,ed = 1;while(1){for(int i = 1; i <= ed; ++i){t = (mul(t,t,n) + c) % n; v = mul(v,Abs(t-s),n);if(i % 127 == 0){LL d = gcd(v,n);if(d > 1) return d;}}LL d = gcd(v,n); if(d > 1) return d;s = t; v = 1; ed <<= 1;           }}void getfactor(LL n){if(n <= sz){while(n != 1) fac[cnt++] = p[n],n /= p[n];return;}if(miller(n,6)) fac[cnt++] = n;else{LL d = n; while(d >= n) d = Pollard_rho(n);getfactor(d); getfactor(n/d);}}int cal(int n,int x) //n的阶乘中，质因子x的次数{int num = 0;while(n){num += n/x;n = n/x;}return num;}int solve(int n,int x,int y){cnt = 0;getfactor(x);map<int,int> mp;int ans = inf;for(int i=0;i<cnt;i++) mp[fac[i]]++; //每个因子出现了多少次for(auto t:mp){int sum = 0;for(int i=1;i<=n;i++) sum += cal(va[i],t.fi); //z中的次数ans = min(ans,(cal(y,t.fi)-sum)/t.se); //y!中的次数减去z中的次数,再除以x中的次数。}return ans;}
}Q;signed main()
{IOS;Q.init(1e5); //记得先要初始化cin>>T;while(T--){cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>va[i];cout<<Q.solve(n,m,k)<<"\n";}return 0;
}

总结：
多多积累经验呀。