SPOJ APS2
题意
令 \(f(i)\) 表示 \(i\) 的最小质因子
求 \[\sum_{i=2}^n f(i)\]
\(n\le 1.234567891011*10^{12}\)
做法
于是单独处理质数部分,然后枚举一个 \(\le
\sqrt{n}\) 的质数,计算贡献
用Min_25筛,求质数的和只需要第一部分即可
复杂度 \(\mathcal
O(\frac{n^{\frac{3}{4}}}{\log n})\)
考虑求合数的贡献
一种做法
令 \(S(a,b)\) 表示 \([2,a]\) 中最小质因子 \(\ge prime_b\) 的数的个数,其中 \(prime_b\) 表示第 \(b\) 个质数
那么合数的答案就是
\[\sum_{prime_i\le \sqrt{n}} S(\lfloor
\frac{n}{prime_i} \rfloor, i) * prime_i\]
使用Min_25筛暴力求 \(S\),可以通过此题
复杂度我不知道
另一种做法
令 \(S(a,b)\) 表示 \([2,a]\)
中是质数或最小质因子 \(\ge
prime_b\) 的数的个数
这可以滚动第二维求,合数的答案是
\[\sum_{prime_i\le \sqrt{n}} \left(
S(\lfloor \frac{n}{prime_i} \rfloor, i) - \left( i-1 \right) \right) *
prime_i\]
要注意去掉质数的数量
在做的过程中计算即可
复杂度 \(\mathcal
O(\frac{n^{\frac{3}{4}}}{\log n})\)
跑得没前一种方法快
又学会了另一种做法..
事实上这里不需要计算第二部分,由于只和最小质因子相关,第一部分里筛掉的数可以直接计算对答案的贡献
这样就肯定比前两种快了
具体可以看代码
代码
在SPOJ上总用时分别为 \(31.13s,49.90s,19.83s\)
第一种做法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include<cstdio> #include<algorithm> #include<ctype.h> #include<string.h> #include<math.h>
using namespace std; #define ll long long #define ull unsigned ll
const int N = 1111115; int T, id, sn, cnt, prime[N]; ll n; ull g[N<<1], a[N<<1], h[N<<1]; bool p[N]; inline int Id(ll x){ return x<=sn?x:id-n/x+1;} ull S(ll a, int b){ if(a<prime[b]) return 0; ll ans=h[Id(a)]-(b-1); for(int i=b; i<=cnt && (ll)prime[i]*prime[i]<=a; ++i){ ans+=S(a/prime[i], i+1)+1; for(ll x=(ll)prime[i]*prime[i]; x*prime[i]<=a; x*=prime[i]) ans+=S(a/x, i+1)+1; } return ans; } int main() { scanf("%d", &T); while(T--){ scanf("%lld", &n), sn=sqrt(n); cnt=id=0; for(ll i=1; i<=n; i=a[id]+1) a[++id]=n/(n/i), g[id]=(a[id]&1?(a[id]+1)/2*a[id]:(ull)a[id]/2*(a[id]+1))-1, h[id]=a[id]-1; for(int i=2; i<=sn; ++i) if(h[i]!=h[i-1]){ prime[++cnt]=i; ull lim=(ull)i*i; for(int j=id, t; a[j]>=lim; --j) g[j]-=i*(g[t=Id(a[j]/i)]-g[i-1]), h[j]-=h[t]-h[i-1]; } ull ans=g[id]; for(int i=1; i<=cnt; ++i) ans+=S(n/prime[i], i)*prime[i]; printf("%llu\n", ans); } return 0; }
|
第二种做法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include<cstdio> #include<algorithm> #include<ctype.h> #include<string.h> #include<math.h>
using namespace std; #define ll long long #define ull unsigned ll
const int N = 1111115; int T, id, sn, cnt, prime[N]; ll n, a[N<<1]; ull g[N<<1], h[N<<1], S[N<<1]; bool p[N]; inline int Id(ll x){ return x<=sn?x:id-n/x+1;} int main() { scanf("%d", &T); while(T--){ scanf("%lld", &n), sn=sqrt(n); cnt=id=0; for(ll i=1; i<=n; i=a[id]+1) a[++id]=n/(n/i), g[id]=(a[id]&1?(a[id]+1)/2*a[id]:(ull)a[id]/2*(a[id]+1))-1, h[id]=a[id]-1; for(int i=2; i<=sn; ++i) if(h[i]!=h[i-1]){ prime[++cnt]=i; ll lim=(ll)i*i; for(int j=id, t; a[j]>=lim; --j) g[j]-=i*(g[t=Id(a[j]/i)]-g[i-1]), h[j]-=h[t]-h[i-1]; } ull ans=g[id]; for(int i=1; i<=id; ++i) S[i]=h[i]; for(int i=cnt; i; --i){ for(int j=id; (ll)prime[i]*prime[i]<=a[j]; --j) for(ll x=prime[i]; x*prime[i]<=a[j]; x*=prime[i]) S[j]+=S[Id(a[j]/x)]-i+1; ans+=(S[Id(n/prime[i])]-i+1)*prime[i]; } printf("%llu\n", ans); } return 0; }
|
第三种代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<cstdio> #include<algorithm> #include<ctype.h> #include<string.h> #include<math.h>
using namespace std; #define ll long long #define ull unsigned ll
const int N = 1111115; int T, id, sn, cnt, prime[N]; ll n, a[N<<1]; ull g[N<<1], h[N<<1]; bool p[N]; inline int Id(ll x){ return x<=sn?x:id-n/x+1;} int main() { scanf("%d", &T); while(T--){ scanf("%lld", &n), sn=sqrt(n); cnt=id=0; for(ll i=1; i<=n; i=a[id]+1) a[++id]=n/(n/i), g[id]=(a[id]&1?(a[id]+1)/2*a[id]:(ull)a[id]/2*(a[id]+1))-1, h[id]=a[id]-1; ull ans=0; for(int i=2; i<=sn; ++i) if(h[i]!=h[i-1]){ prime[++cnt]=i; ll lim=(ll)i*i; for(int j=id, t; a[j]>=lim; --j){ g[j]-=i*(g[t=Id(a[j]/i)]-g[i-1]), h[j]-=h[t]-h[i-1]; if(j==id) ans+=(h[t]-h[i-1])*i; } } printf("%llu\n", ans+g[id]); } return 0; }
|