2019西安邀请赛（部分题解)

  1 #include <set>
  2 #include <map>
  3 #include <deque>
  4 #include <queue>
  5 #include <stack>
  6 #include <cmath>
  7 #include <ctime>
  8 #include <bitset>
  9 #include <cstdio>
 10 #include <string>
 11 #include <vector>
 12 #include <cstdlib>
 13 #include <cstring>
 14 #include <iostream>
 15 #include <algorithm>
 16 #include <unordered_map>
 17 using namespace std;
 18 
 19 typedef long long LL;
 20 typedef pair<LL, LL> pLL;
 21 typedef pair<LL, int> pLi;
 22 typedef pair<int, LL> pil;;
 23 typedef pair<int, int> pii;
 24 typedef unsigned long long uLL;
 25 
 26 #define lson rt<<1
 27 #define rson rt<<1|1
 28 #define lowbit(x) x&(-x)
 29 #define name2str(name) (#name)
 30 #define bug printf("*********\n")
 31 #define debug(x) cout<<#x"=["<<x<<"]" <<endl
 32 #define FIN freopen("D://code//in.txt","r",stdin)
 33 #define IO ios::sync_with_stdio(false),cin.tie(0)
 34 #define long long
 35 const double eps = 1e-8;
 36 const int mod = 1000000007;
 37 const int maxn = 1e7 + 3;
 38 const double pi = acos(-1);
 39 const int inf = 0x3f3f3f3f;
 40 const LL INF = 0x3f3f3f3f3f3f3f3fLL;
 41 
 42 bool v[maxn];
 43 int n, m, p, cnt, MOD;
 44 int isp[maxn/10], phi[maxn];
 45 int sum[maxn], ssum[maxn];
 46 unordered_map<int, int> dp1, dp2;
 47 typedef long long ll;
 48 
 49 int add(int x, int y) {
 50     if(y < 0) x += y;
 51     else x = x - MOD + y;
 52     if(x < 0) x += MOD;
 53     return x;
 54 }
 55 
 56 
 57 void init() {
 58     phi[1] = ssum[1] = 1;
 59     for(int i = 2; i < maxn; ++i) {
 60         if(!v[i]) {
 61             ssum[i] = 2;
 62             phi[i] = i - 1;
 63             isp[cnt++] = i;
 64         }
 65         for(int j = 0; j < cnt && i * isp[j] < maxn; ++j) {
 66             v[i*isp[j]] = 1;
 67             if(i % isp[j] == 0) {
 68                 phi[i*isp[j]] = phi[i] * isp[j];
 69                 int pp = 1, x = i;
 70                 while(x % isp[j] == 0) x /= isp[j], pp++;
 71                 ssum[i*isp[j]] = ssum[i] / pp * (pp + 1);
 72                 break;
 73             }
 74             phi[i*isp[j]] = phi[i] * (isp[j] - 1);
 75             ssum[i*isp[j]] = ssum[i] * 2;
 76         }
 77     }
 78     for(int i = 1; i < maxn; ++i) {
 79         sum[i] = add(sum[i-1], phi[i]);
 80         ssum[i] = add(1LL * ssum[i] * i % MOD, ssum[i-1]);
 81     }
 82        // for(int i=3e6-20;i<3e6;i++)cout<<ssum[i]<<" " ;puts("");
 83 
 84 }
 85 
 86 
 87 
 88 int getphi(int x) {
 89     if(x < maxn) return sum[x];
 90     if(dp1[x]) return dp1[x];
 91     int ans = (1LL * x * (x + 1) / 2) % MOD;
 92     for(int l = 2, r; l <= x; l = r + 1) {
 93         r = x / (x / l);
 94         int tmp = 1LL * (r - l + 1) * getphi(x/l) % MOD;
 95         ans = add(ans, -tmp);
 96     }
 97     return dp1[x] = ans;
 98 }
 99 
100 int qpow(int x, int n) {
101     int res = 1;
102     while(n) {
103         if(n & 1) res = 1LL * res * x % p;
104         x = 1LL * x * x % p;
105         n >>= 1;
106     }
107     return res;
108 }
109 
110 int getnum(int x) {
111    if(x < 3e6) return ssum[x];
112     //if(dp2[x]) return dp2[x];
113     int ans = 0;
114     for(int l = 1, r; l <= x; l = r + 1) {
115         r = x / (x / l);
116         LL tmp1 = 1LL * ((x / l) + 1) * (x / l);
117         LL tmp2 = 1LL * (l + r) * (r - l + 1) / 2;
118         ans = add(ans, tmp1 * tmp2 / 2 % MOD);
119     }
120     return dp2[x] = ans;
121 }
122 
123 signed main(){
124     scanf("%d%d%d", &n, &m, &p);
125     MOD = p - 1;
126     init();
127     int ans2 = getnum(n);
128     int ans1 = 0;
129     for(int l = 1, r; l <= n; l = r + 1) {
130         r = n / (n / l);
131         int tmp1 = getphi(n / l);
132         int tmp2 = add(getnum(r), -getnum(l-1));
133         ans1 = add(ans1, 1LL * tmp1 * tmp2 % MOD);
134     }
135     ans1 = 2LL * ans1 % MOD;
136     int ans = add(ans1, -ans2);
137     printf("%d\n", qpow(m, ans));
138     return 0;
139 }