C++14(g++5.4) 解法, 执行用时: 729ms, 内存消耗: 11872K, 提交时间: 2018-10-27 20:17:54

#include <bits/stdc++.h>
using namespace std;
#define N 100001
int pw(int a,int b,int M){
    int res=1;
    for (;b;b>>=1,a=1LL*a*a%M) if (b&1) res=1LL*res*a%M;
    return res;
}
int n;
vector<int>V[N];
int ans[N],cnt[N];
int main(){
    scanf("%d",&n);
    for (int i=2;i<N;i++) for (int j=i;j<N;j+=i) V[j].push_back(i);
    for (int i=1;i<=n;i++){
        int x,k,M; scanf("%d%d%d",&x,&k,&M);
        cnt[1]++; ans[1]=cnt[1];
        for (int i:V[x]) cnt[i]++,ans[i]=cnt[i];
        for (vector<int>::iterator it=V[x].end();it--!=V[x].begin();){
            for (int p:V[x/(*it)]) ans[*it]-=ans[*it *p];
        }
        for (int p:V[x]) ans[1]-=ans[p];
        int Ans=0;
        for (int p:V[x]) if (ans[p]) (Ans+=1LL*ans[p]*pw(p,k,M)%M)%=M;
        if (ans[1]) (Ans+=ans[1])%=M;
        printf("%d\n",Ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 635ms, 内存消耗: 12256K, 提交时间: 2018-10-31 13:27:48

#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int n,ans,f[N],g[N];
const int m=100000;
vector<int>v[N];
ll Pow(ll a,int b,int mod){
  ll res=1;
  while(b){
    if(b&1)res=res*a%mod;
    a=a*a%mod;b>>=1;
  }
  return res;
}
int main()
{
  int x,y,k,p;
  scanf("%d",&n);
  for(int i=1;i<=m;i++)
    for(int j=i;j<=m;j+=i)v[j].push_back(i); 
  while(n--)
  {
    scanf("%d%d%d",&x,&k,&p);ans=0;
    for(int i=0;i<v[x].size();i++)f[v[x][i]]++;
    for(int i=v[x].size()-1;i>=0;i--)
	{
	  y=v[x][i];g[y]+=f[y];
	  if(g[y]<=0)continue;
	  ans=(ans+(ll)Pow(y,k,p)*g[y])%p;
	  for(int j=0;j<v[y].size();j++)g[v[y][j]]-=g[y];
	  g[y]=0;
	}
	printf("%d\n",ans);
  }
  return 0;
}

pypy3 解法, 执行用时: 2299ms, 内存消耗: 55948K, 提交时间: 2022-04-20 22:21:26

N = 100001
factors = [[] for i in range(N)]

for i in range(1, N):
    for j in range(i, N, i):
        factors[j].append(i)

f_cnt = [0] * N
cnt = [0] * N

n = int(input())
for _ in range(n):
    ans = 0
    x, k, p = map(int, input().split())
    for f in factors[x]:
        f_cnt[f] += 1
    
    for y in factors[x][::-1]:
        cnt[y] += f_cnt[y]
        if cnt[y]:
            ans = (ans + cnt[y]*pow(y,k,p)) % p
            for yf in factors[y]:
                cnt[yf] -= cnt[y]
            cnt[y] = 0
    print(ans)