我的想法是这样的：用min25筛出质数个数

然后枚举根号下的质数和次幂，然后计算贡献。

是我的方法有问题，还是代码实现有问题。

求大佬帮忙

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long prime[400005],cnt;
long long n,sqr,tot,w[800005],g[800005],ind1[400005],ind2[400005],s,t,g_po[45];
long long st1;
bool vis[400005];
long long fpow(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(){
	st1=fpow(1+s,t);
	vis[1]=1;
	for(int i=2;i<=sqr;i++){
		if(!vis[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=sqr;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	long long l=1;
	while(l<=n){
		long long r=(n/(n/l));
		tot++;
		w[tot]=n/l;
		g[tot]=n/l-1%mod;
		if(n/l<=sqr)ind1[n/l]=tot;
		else ind2[n/(n/l)]=tot;
		l=r+1;
	}
	
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=tot&&prime[i]*prime[i]<=w[j];j++){
			int k=w[j]/prime[i]<=sqr? ind1[w[j]/prime[i]]:ind2[n/(w[j]/prime[i])];
			g[j]=(g[j]-(g[k]-(j-1))%mod+mod)%mod;
		}
	}
	for(int i=1;i<=tot;i++){
		cout<<w[i]<<" "<<g[i]<<endl;
	}
}
long long ans=1;
int main(){
	cin>>n>>s>>t;
	sqr=sqrt(n);
	init();
	g_po[1]=fpow(1+s,t)-2;
	for(int i=2;i<=40;i++){
		g_po[i]=(fpow(1+i*s,t)%mod-2*fpow(1+(i-1)*s,t)%mod+fpow(1+(i-2)*s,t)%mod+2*mod)%mod;
	}
	for(int i=1;i<=cnt;i++){
		long long pe=prime[i]%mod;
		for(int e=1;pe<=n;pe*=prime[i],e++){
			ans=ans*fpow(g_po[e],(n/pe-n/(pe*prime[i])))%mod;
			
		}
	}
	ans=ans*fpow(g_po[1],g[ind2[n/sqr]])%mod;
	cout<<ans<<endl;
	
}