题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6265
思路：
首先要确定欧拉函数的一个特例 phi(1) = 1； 在欧拉函数的公式中 phi (n) = n*(1-q1)*(1-q2)*(1-q3)..... 只有n == 1的时候是不适用这个公式的；
其次，题目中要求的公式虽然感觉很复杂，但事实上，只要对公式整理一下，就能发现题目有很多地方是帮你化简了问题的，比如：在公式 phi(3)*n/3 中的分母 3是可以和分子中phi(3)抵消的，因为phi (3) = 3*(1-1/3)；所以 phi(3)*n/3 == (1-1/3)*n；这个化简有什么作用？如果phi 没了前面的n，那么phi(6)/6 是等于 phi(36)/36 (只要两个数n1和n2 所包含的素数相同那么 phi(n1)/n1 == phi(n2)/n2)；这个问题可以自己通过欧拉函数检验一下；
这里以36为例：
36的因数有 1,2,3,4,6,9,12,18,36；这些数分别用素数的乘积来表示会发现，他们都是由36包含的素数组成；而且2*3组合有2*2个，这两个2分别是 2^2 * 3^2的幂；那么问题就转变成 素数乘积的组合了；
解题方法有两种；
dfs（要用G++交题） 把n的素数个数与对应素数存起来，然后dfs取和不取的情况，就能得到对应的解；
第二种是直接写成公式：
知道欧拉函数的推导过程就不会难理解下面的公式：（+1是能不取这个素数的情况）
下面引用这个博客的图片：https://blog.csdn.net/weixin_38327682/article/details/79988278
#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; typedef long long ll; const int Mod = 998244353; const int Maxn = 1e8+10; ll inv[Maxn]; int m, ans, p[50], q[50]; //int pow_mod (int a, int n) { // if (n == 0) return 1; // int x = pow_mod (a, n/2); // ll ans = (ll)x*x % Mod; // if (n & 1) ans = ans*a % Mod; // return (int)ans; //} ll pow_mod (int a, int n) { ll ret = 1; while (n) { if (n & 1) ret = ret*a % Mod; a = (ll)a*a % Mod; n >>= 1; } return ret; } void dfs (int step, int sum) { if (step == m) { ans = (ans+sum) % Mod; return; } int t = (ll)sum*(p[step]-1)%Mod*inv[p[step]]%Mod*q[step]%Mod; dfs (step+1, t); dfs (step+1, sum); } int main (void) { int t; scanf ("%d", &t); while (t--) { scanf ("%d", &m); int n = 1; for (int i = 0; i < m; ++i) { scanf ("%d%d", p+i, q+i); n = (ll)n*pow_mod (p[i], q[i]) % Mod; inv[p[i]] = pow_mod (p[i], Mod-2); } ans = 0; dfs (0, n); printf ("%d\n", ans); } return 0; }第二种：
#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; typedef long long ll; const int Mod = 998244353; const int Maxn = 1e8+10; //int pow_mod (int a, int n) { // if (n == 0) return 1; // int x = pow_mod (a, n/2); // ll ans = (ll)x*x % Mod; // if (n & 1) ans = ans*a % Mod; // return (int)ans; //} ll pow_mod (int a, int n) { ll ret = 1; while (n) { if (n & 1) ret = ret*a % Mod; a = (ll)a*a % Mod; n >>= 1; } return ret; } int main (void) { int t, m; scanf ("%d", &t); while (t--) { scanf ("%d", &m); ll ans = 1, n = 1, p, q; for (int i = 0; i < m; ++i) { scanf ("%lld%lld", &p, &q); n = n*pow_mod (p, q) % Mod; ans = ans*(q*(p-1)%Mod*pow_mod(p, Mod-2)%Mod+1) % Mod; } ans = ans*n % Mod; printf ("%lld\n", ans); } return 0; }
