此题也因为测评姬抖动的情况,有点轻微卡常,多交几次还是能过的
思路
- 可以先把10的倍数预处理
进行4e6的欧拉筛
然后对每个数进行分解质因数
分解质因数的时候我们可以把之前的数分解得出的答案存起来,对之后分解质因数进行优化
代码
// Problem: 牛牛的“质因数” // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9982/I // Memory Limit: 524288 MB // Time Limit: 2000 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=4e6+10; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); ll f[N],g[105],ans; string s[N]; int prime[N],cnt=0; //prime数组存放所以素数,cnt为素数个数 bool st[N]; //false为素数 void get_prime(int n){ for(int i=2;i<=n;i++){ if(!st[i]) prime[cnt++]=i; //把素数i存到prime数组中 for(int j=0;j<cnt&&i*prime[j]<=n;j++){ st[i*prime[j]]=true; //找到的素数的倍数不访问 if(i%prime[j]==0) break; //关键代码 } } } string fenjie(int x){ string str=""; for(int i=0;i<cnt;i++){ int p=prime[i]; if(x%p==0){ x/=p; str+=to_string(p); } if(x==1) break; if(!st[x]){ str+=to_string(x); break; } if(!s[x].empty()){ str+=s[x]; break; } } return str; } void solve(){ int n;cin>>n; get_prime(n); // debug(cnt); for(int i=2;i<=n;i++){ if(!st[i]) f[i]=i; else{ s[i]=fenjie(i); // debug(s); int len=s[i].size()-1; for(int j=0;j<=len;j++){ f[i]+=1ll*(s[i][j]-'0')*g[len-j]%mod; f[i]%=mod; } } } rep(i,2,n) ans+=f[i],ans%=mod; cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) g[0]=1; rep(i,1,100) g[i]=g[i-1]*10,g[i]%=mod; solve(); return 0; }