————————————————————————-
UOJ#188. 【UR #13】Sanrd
递归版
求L-R每个数的次大质因子（2*3*3为3，质数为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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define Get_ID(x) ((x<=X)?ID1[x]:ID2[n/(x)]) using namespace std; const int N=1000010; ll L,R,X,prime[N],W[N],ID1[N],ID2[N],g[N]; int num,cnt; bool flag[N]; void Get_prime(int n) { num=0; for (int i=2;i<=n;i++) { if (!flag[i]) prime[++num]=i; for (int j=1;j<=num&&i*prime[j]<=n;j++) { flag[i*prime[j]]=1; if (i%prime[j]==0) break; } } } ll dfs(ll n,ll x,ll y) { if (x<=1||prime[y]>x) return 0; ll ans=prime[y-1]*(g[Get_ID(x)]-(y-1)); for (int i=y;i<=num&&prime[i]*prime[i]<=x;i++) { for (ll e=prime[i];e*prime[i]<=x;e*=prime[i]) ans+=dfs(n,x/e,i+1)+prime[i]; } return ans; } ll solve(ll n) { X=trunc(sqrt(n)); Get_prime(X); cnt=0; for (ll i=1,j;i<=n;i=j+1) { j=n/(n/i); W[++cnt]=n/i; if (n/i<=X) ID1[n/i]=cnt; else ID2[j]=cnt; } for (int i=1;i<=cnt;i++) g[i]=W[i]-1; for (int i=1;i<=num;i++) { for (int j=1;j<=cnt&&prime[i]*prime[i]<=W[j];j++) g[j]-=g[Get_ID(W[j]/prime[i])]-(i-1); } return dfs(n,n,1); } int main() { scanf("%lld%lld",&L,&R); printf("%lld\n",solve(R)-solve(L-1)); return 0; } |
LOJ#6053. 简单的函数
非递归版
求1-N的积性函数的和。
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long #define mo 1000000007 #define inv 500000004 using namespace std; const int N=200100; ll n,f[N],prime[N],sum[N],g[N],number[N],W[N],ID1[N],ID2[N]; int cnt,num; bool flag[N]; void Get_Prime(int n) { cnt=0; for (int i=2;i<=n;i++) { if (!flag[i]) prime[++cnt]=i,sum[cnt]=(sum[cnt-1]+prime[cnt])%mo; for (int j=1;j<=cnt&&i*prime[j]<=n;j++) { flag[i*prime[j]]=1; if (i%prime[j]==0) break; } } } ll Get(ll n,ll X) { for (int i=1;i<=num;i++) f[i]=(g[i]-number[i]+((W[i]>=2)?2:0)+mo)%mo; for (int i=cnt;i>=1;i--) { for (int j=1;j<=num&&prime[i]*prime[i]<=W[j];j++) { for (ll e=prime[i],num=1;e*prime[i]<=W[j];e*=prime[i],num++) { int k=(W[j]/e<=X)?ID1[W[j]/e]:ID2[n/(W[j]/e)]; ll y=(sum[i]-i+((W[k]>=2)?2:0)+mo)%mo; f[j]=(f[j]+(prime[i]^num)%mo*(f[k]-y+mo)%mo+(prime[i]^(num+1))%mo)%mo; } } } return (f[1]+1)%mo; } ll solve(ll n) { ll X=sqrt(n); Get_Prime(X); num=0; for (ll i=1,j;i<=n;i=j+1) { j=n/(n/i); W[++num]=n/i; if (n/i<=X) ID1[n/i]=num; else ID2[j]=num; } for (int i=1;i<=num;i++) { ll w=W[i]%mo; g[i]=(w*(w+1)%mo*inv%mo-1+mo)%mo; number[i]=(W[i]-1)%mo; } for (int i=1;i<=cnt;i++) { for (int j=1;j<=num&&prime[i]*prime[i]<=W[j];j++) { int k=(W[j]/prime[i]<=X)?ID1[W[j]/prime[i]]:ID2[n/(W[j]/prime[i])]; g[j]=(g[j]-(g[k]-sum[i-1]+mo)%mo*prime[i]%mo+mo)%mo; number[j]=(number[j]-number[k]+(i-1)+mo)%mo; } } return Get(n,X); } int main() { scanf("%lld",&n); printf("%lld\n",solve(n)); return 0; } |
BZOJ5244: [Fjwc2018]最大真因数
非递归版
求L-R每个数i/(i的最小质因子)的和。
|
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 44 45 46 47 48 49 50 51 52 |
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long using namespace std; const int N=500010; ll L,R,W[N],ID1[N],ID2[N],f[N],prime[N],sum[N]; int cnt; bool flag[N]; void Get_Prime(ll X) { cnt=0; for (int i=2;i<=X;i++) { if (!flag[i]) prime[++cnt]=i,sum[cnt]=sum[cnt-1]+i; for (int j=1;j<=cnt&&i*prime[j]<=X;j++) { flag[i*prime[j]]=1; if (i%prime[j]==0) break; } } } ll solve(ll n) { ll X=trunc(sqrt(n)); Get_Prime(X); int num=0; for (ll i=1,j;i<=n;i=j+1) { j=n/(n/i); W[++num]=n/i; if (n/i<=X) ID1[n/i]=num; else ID2[j]=num; } for (int i=1;i<=num;i++) f[i]=(W[i]&1)?((W[i]+1)/2*W[i]-1):(W[i]/2*(W[i]+1)-1); ll ans=0; for (int j=1;j<=cnt;j++) for (int i=1;i<=num&&prime[j]*prime[j]<=W[i];i++) { int k=(W[i]/prime[j]<=X)?ID1[W[i]/prime[j]]:ID2[n/(W[i]/prime[j])]; f[i]-=prime[j]*(f[k]-sum[j-1]); if (i==1) ans+=f[k]-sum[j-1]; } return ans; } int main() { scanf("%lld%lld",&L,&R); printf("%lld\n",solve(R)-solve(L-1)); return 0; } |
