#include<bits/stdc++.h>
#define int long long
using namespace std;
int pr[100000005],t,n,ans=1;
bool vis[100000005];
int _log(int x,int y){
int res=1;
for(;res<=x;res=res*y%10000007);
return res;
}
signed main(){
cin>>n;
for(int i=2;i<=n;i++){
if(vis[i]==0){
pr[++t]=i;
ans*=_log(n,i),ans%=100000007;
cout<<_log(n,i)<<" "<<ans<<'\n';
}
for(int j=1;j<=t&&i*pr[j]<=n;j++){
vis[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}
cout<<ans;
return 0;
}
1 个赞
虽然不知道怎么做，但是你为什么没开long long
#define int long long
帮忙调调呗
哦，但是我数论真不好，n的范围多少，还有样例给一下
luogu P4626，这道题 A 了就是我的第二十道蓝了
改到90了（TLE，最后一点差70ms）
代码给我看看
不要define，for里面用int减少时间
对着题解调的：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e8+7;
int pr[100000005],t,n,ans=1;
bitset<100000005>vis;
int _log(int x,int y){
int res=1;
for(;res<=x;res=res*y);
res/=y;
return res;
}
signed main(){
cin>>n;
for(int i=2;i<=n;i++){
if(vis[i]==0){
pr[++t]=i;
ans*=_log(n,i),ans%=mod;
}
for(int j=1;j<=t&&i*pr[j]<=n;j++){
vis[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}
cout<<ans;
return 0;
}
不要用define
主函数for循环里用int这样更快
《1.00s》
差1ms也是差（doge）
完了，复杂度似乎不对
啊？496ms，差这么多？
改了，但……
