递推 2017CCPC杭州站现场赛B题 Master of Phi 欧拉函数
程序员文章站
2022-03-30 23:31:55
...
http://acm.hdu.edu.cn/showproblem.php?pid=6265
2017CCPC杭州站现场赛B题
题目大意:给你一个数n的因数及其指数pi,qi,对于其所有的因数d,求
题解:题中给了一个求欧拉函数的公式
欧拉函数的公式可以变形为下面这种形式,即 把 m 拆分成 pi 的 hi 次方的乘积后,把每个质因子pi都乘进去一个。
其中 pi 是 m 的质因子, hi 是 m 对 pi 的指数。
然后我们分析一下题目给的求和公式里的每一项
在 d 的欧拉函数后面乘以 n/d,算一算会发现最后的结果是 在 n 中且不在 d 中的质因子的指数是 q[i] (n的质因子指数), 在 d 中的质因子的指数是 q[i]-1,且还要乘以一个 (p[i]-1) 。推理过程如下:
pi 是 d 的质因子:
pi 不是 d 的质因子:
然后我们枚举所有的选取质因子的情况,会得到下面的递推式:
草稿纸上写的有点乱,将就着看吧。。。。。。
放上学长代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include<ctime>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int N = 220;
const int MOD = 998244353;
int n;
int p[N], q[N];
ll s1[N], s2[N];
ll quick(ll a, int b) {
ll ans = 1;
while(b) {
if (b % 2 == 1) ans = ans * a % MOD;
a = a * a % MOD;
b /= 2;
}
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d%d", p + i, q + i);
for(int i = 0; i < n; i++) s1[i] = quick(p[i], q[i] - 1), s2[i] = s1[i] * p[i] % MOD;
for(int i = 0; i < n; i++) s1[i] = s1[i] * (p[i] - 1) % MOD;
ll ans = 1;
for(int i = 0; i < n; i++) {
ll t = s1[i] * q[i] % MOD;
t = (t + s2[i]) % MOD;
ans = ans * t % MOD;
}
printf("%lld\n", ans);
}
return 0;
}
放一种没有改动方程的写法,也是用的递推。 只不过在要求的式子里的n/d和欧拉函数里的d约掉了,剩下的就是(1-1/p)的累乘。同样的,枚举质因子的选举情况,然后递推即可。
通过这份代码,我学到了许多,比如
求逆元(1/p),(在mod一个质数的情况下)
对一个负数取mod。
ans = (ans%mod + mod)%mod;
#include <cstdio>
const long long mod=998244353;
typedef long long ll;
ll p[50], q[50];
ll pow(ll x,ll n,ll mod)
{
ll res=1;
while(n>0)
{
if(n&1)
{
res=res*x;
res=res%mod;
}
x=x*x;
x=x%mod;
n>>=1;
}
return res;
}
ll extgcd(ll a,ll b,ll &x,ll &y){
if(b!=0){
ll r=extgcd(b,a%b,y,x);
y-=(a/b)*x;
return r;
}else{
x=1,y=0;
return a;
}
}
ll inverse(ll a){
ll x,y;
extgcd(a,mod,x,y);
return (mod+x%mod)%mod;
}
int main()
{
int t, n;
long long m,sum, ans;
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
scanf("%d", &n);
m = 1;
for (int j = 0; j < n; j++)
{
scanf("%lld%lld", &p[j], &q[j]);
m*=pow(p[j], q[j], mod)% mod;
m%=mod;
}
sum = m;
for (int j = 0; j < n; j++)
{
ans = -inverse(p[j]);
ans = (ans%mod + mod)%mod;
ans = 1+q[j]*(ans+1);
ans %= mod;
sum=sum * ans % mod;
}
printf("%lld\n",sum );
}
return 0;
}