hdu5728 PowMod

淡淡的烟草味﹌ 2021-12-20 10:33 87阅读 0赞

[hdu5728 PowMod][]

> 给定 \\(n,\\ m,\\ p\\) ，令 \\(k=\\displaystyle\\sum\_\{i=1\}^m\\varphi(i\\times n)\\pmod\{10^9+7\}\\)
> 
> 求 \\(k^\{k^\{k^\{\\cdots^\{k\}\}\}\}\\pmod\{p\}\\)
> 
> 共 \\(T\\) 组询问， \\(n\\) 无平方因子
> 
> \\(T\\leq100,\\ n,\\ m,\\ p\\leq10^7\\)

数论，计数

--------------------

令 \\(f(n,\\ m)=\\displaystyle\\sum\_\{i=1\}^m\\varphi(i\\times n)\\) 。假设 \\(p\\) 是 \\(n\\) 的一个质因子，若 \\((i,\\ n)=1\\) ，则 \\(\\varphi(i\\times n)=\\varphi(i)\\times\\varphi(n)\\) ，否则若 \\(p\\ |\\ i\\) ，可以将 \\(i\\) 看作 \\(k\\times p\\) ，否则 \\(p\\not |\\;i\\) ，于是分类讨论

\\\[\\begin\{aligned\}f(n,\\ m)&=\\displaystyle\\sum\_\{i=1\}^m\{\[p\\ |\\ i\](\\varphi(p)\\times\\varphi(i\\times\\frac\{n\}\{p\}))\}+\\sum\_\{i=1\}^\{\\frac\{m\}\{p\}\}\\varphi(i\\times n\\times p)\\\\&=\\varphi(p)\\times\\sum\_\{i=1\}^m\{\[p\\not|\\;i\]\\varphi(i\\times\\frac\{n\}\{p\})+p\\times\\sum\_\{i=1\}^\{\\frac\{m\}\{p\}\}\\varphi(i\\times n)\}\\\\&=\\varphi(p)\\times\\sum\_\{i=1\}^m\{\[p\\not|\\;i\]\\varphi(i\\times\\frac\{n\}\{p\})+(\\varphi(p)+1)\\times\\sum\_\{i=1\}^\{\\frac\{m\}\{p\}\}\\varphi(i\\times n)\}\\\\&=\\varphi(p)\\times\\sum\_\{i=1\}^m\{\[p\\not|\\;i\]\\varphi(i\\times\\frac\{n\}\{p\})\}+\\varphi(p)\\times\\sum\_\{i=1\}^\{\\frac\{m\}\{p\}\}\\varphi(i\\times n)+\\sum\_\{i=1\}^\{\\frac\{m\}\{p\}\}\\varphi(i\\times n)\\end\{aligned\}\\\]

但前两项是可以合并的，第二项恰好将第一项补全了，于是

\\\[f(n,\\ m)=\\varphi(p)\\times\\sum\_\{i=1\}^m\\varphi(i\\times\\frac\{n\}\{p\})+\\sum\_\{i=1\}^\{\\frac\{m\}\{p\}\}\\varphi(i\\times n)\\\]

所以 \\\[f(n,\\ m)=\\varphi(p)\\times f(\\frac\{n\}\{p\},\\ m)+f(n,\\ \\frac\{m\}\{p\})\\\]

递归时枚举一个质因子就够了

而求 \\(k^\{k^\{k^\{\\cdots^\{k\}\}\}\}\\pmod\{p\}\\) 直接用欧拉定理就可以了

时间复杂度 \\(O(\\) 能过 \\()\\)

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e7 + 10, P = 1e9 + 7;
    int tot, p[maxn], phi[maxn], sum[maxn];
    
    inline int inc(int x, int y) {
      return x + y < P ? x + y : x + y - P;
    }
    
    inline int qp(int a, int k, int P) {
      int res = 1;
      for (; k; k >>= 1, a = 1ll * a * a % P) {
        if (k & 1) res = 1ll * res * a % P;
      }
      return res;
    }
    
    void sieve() {
      int N = 10000000;
      for (int i = 2; i <= N; i++) {
        if (!p[i]) p[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * p[j] <= N; j++) {
          p[i * p[j]] = 1;
          if (i % p[j] == 0) {
            phi[i * p[j]] = phi[i] * p[j]; break;
          }
          phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
      }
      phi[1] = 1;
      for (int i = 1; i <= N; i++) {
        sum[i] = inc(sum[i - 1], phi[i]);
      }
    }
    
    int dfs(int a, int P) {
      int t = phi[P];
      return t == 1 ? 0 : qp(a, dfs(a, t) % t + t, P);
    }
    
    int calc(int n, int m) {
      if (!m) return 0;
      if (n == 1) return sum[m];
      int tmp = sqrt(n);
      for (int i = 2; i <= tmp; i++) {
        if (n % i == 0) {
          return (calc(n, m / i) + 1ll * phi[i] * calc(n / i, m)) % P;
        }
      }
      return (calc(n, m / n) + 1ll * phi[n] * sum[m]) % P;
    }
    
    int main() {
      sieve();
      int n, m, p;
      while (~scanf("%d %d %d", &n, &m, &p)) {
        printf("%d\n", dfs(calc(n, m), p));
      }
      return 0;
    }

转载于:https://www.cnblogs.com/Juanzhang/p/11044555.html

[hdu5728 PowMod]: http://acm.hdu.edu.cn/showproblem.php?pid=5728