Product

You are given positive integers $n$ ( $n \le 10^9$), $m$ ( $m \le 2 \times 10^9$), $p$ ($p \le 2 \times 10^9$) and you need to calculate the following product modulo $p$.

Input

Each test file contains a single test case. In each test file:

There are three positive integers $n$, $m$, $p$ which are separated by spaces. It is guaranteed that $p$ is a prime number.

Output

An integer representing your answer.

样例输入1

1
2 2 1000000007

样例输出1

1
128

样例输入2

1
233 131072 4894651

样例输出2

1
748517

样例输入3

1
1000000000 999999997 98765431

样例输出3

1
50078216

题意

请看题目描述

解决方案

对原式进行化简：

先考虑指数部分：

首先考虑后面一部分，可以用杜教筛求出其前缀和，回顾一下杜教筛的推导过程：

其中 $g(n)$ 是需要我们自己构造的函数。

用杜教筛求 $\phi(n)$ 的前缀和时，我们令 $g(n) = I(n)$ ，则 $h(n) = id(n)$ ，所以有：

后面一部分可以用杜教筛分块了，那前面一部分的前缀和呢？

推导如下：

之后，这一部分也可以分块解决了，至此，此题公式推导完毕。

但是还没有结束，因为我们只是处理了指数部分，实际要求的是一个乘方。很明显感觉到，这个指数是会爆 long long 的，那么就要考虑欧拉降幂，题目也明说了答案对 $p$ 取模，且 $p$ 是一个质数，所以必有 $\gcd(m,p)=1$ ，那么结合欧拉降幂的公式，可得：

所以在公式中分块求和的时候记得对 $p - 1$ 取模，最后再跑一个快速幂就好了。

代码

注意要把 $k\cdot d(k)$ 也筛出来一部分，不然会 T。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 8e6 + 10;

ll mod;
bool vis[maxn];
int prime[maxn];
ll phi[maxn];
ll d[maxn];
int low[maxn];
int tot;

unordered_map<int, ll> mp;

void eular() {
  vis[0] = vis[1] = true;
  phi[1] = d[1] = 1;
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) {
      prime[tot++] = i;
      phi[i] = i - 1;
      d[i] = 2;
      low[i] = 1;
    }
    for (int j = 0; j < tot && i * prime[j] < maxn; j++) {
      vis[i * prime[j]] = true;
      if (i % prime[j]) {
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        d[i * prime[j]] = d[i] * 2;
        low[i * prime[j]] = 1;
      } else {
        phi[i * prime[j]] = phi[i] * prime[j];
        d[i * prime[j]] = d[i] / (low[i] + 1) * (low[i] + 2);
        low[i * prime[j]] = low[i] + 1;
        break;
      }
    }
  }
  for (int i = 1; i < maxn; i++) {
    phi[i] = (phi[i - 1] + phi[i]) % mod;
    d[i] = (i * d[i] + d[i - 1]) % mod;
  }
}

ll get_sum(int x) {
  if (x < maxn) {
    return d[x];
  }
  ll ans = 0;
  for (int l = 1, r; l <= x; l = r + 1) {
    r = x / (x / l);
    ll t1 = (1ll * (l + r) * (r - l + 1) / 2) % mod;
    ll t2 = (1ll * (x / l) * (x / l + 1) / 2) % mod;
    ans = (ans + t1 * t2) % mod;
  }
  return ans;
}

ll djs_phi(int x) {
  if (x < maxn) {
    return phi[x];
  }
  if (mp.count(x)) {
    return mp[x];
  }
  ll ans = 0;
  for (int l = 2, r; l <= x; l = r + 1) {
    r = x / (x / l);
    ans += (r - l + 1) * djs_phi(x / l) % mod;
    ans %= mod;
  }
  ll tmp = (1ll * x * (x + 1) / 2) % mod;
  ans = (tmp - ans + mod) % mod;
  return mp[x] = ans;
}

ll quick_mod(ll a, ll b, ll c) {
  a %= c;
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = ans * a % c;
    }
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}

int main() {
  int n, m, p;
  scanf("%d%d%d", &n, &m, &p);
  mod = p - 1;
  eular();
  ll sum = 0;
  for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ll t1 = get_sum(r) - get_sum(l - 1);
    t1 = (t1 + mod) % mod;
    ll t2 = 2 * djs_phi(n / l) - 1;
    sum = (sum + t1 * t2) % mod;
  }
  printf("%lld\n", quick_mod(m, sum, p));
  return 0;
}