D - Sigma Function
这道题一看到就和上一道题很像，以为也是算数基本定理的考查，做了一下，发现能过样例……tle……
tle的思路：经过多次验算？？？就是发现幂的规律吧，只要存在一个pi,ei都为奇数的pi^ei,就能使sum为偶数。(素因子分解后，全为奇 ^ 偶，偶 ^ 偶，偶 ^ 奇，因子和就是奇数。)
tle的代码做个借鉴：
//输出格式没改 #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define MAX 1000005 #define mod 1000000007 using namespace std; long long p[MAX],v[MAX],num_prime; void GetPriem()//获得素数 { memset(p,0,sizeof(p)); memset(v,0,sizeof(v)); for(int i=2;i<MAX;i++) { if(!v[i]) { p[++num_prime]=i; for(int j=i;j<MAX;j+=i) v[j]=1; } } } long long Ans(long long n) { long long cnt,sum=0; for(int i=1;i<=num_prime && p[i]<=n;i++) { if(n%p[i]==0) { cnt=0; while(n%p[i]==0) { cnt++; n/=p[i]; } if(cnt % 2 != 0 && p[i] % 2 != 0) { sum = 1; } } } if(n > 1) sum = 1; return sum; } int main() { GetPriem(); int T,cnt=1,i,j; long long n,m; scanf("%d",&T); while(T--) { scanf("%lld",&n); long long m = 0; for(int k = 1;k <= n;k++) { m += Ans(k); } cout<<m<<endl; } return 0; }
题解：
打表找规律。
素因子分解打表计算前n项和判断奇数偶数可以发现如下规律：
只要是2 ^ x,a ^ 2,2 * a ^ 2…只有这种数的因子和是奇数。所以，我们直接去重即可。
但是这些直接去重我们会发现减去的这些值有重复的，所以我们要判断下。
i (代表x||a): 0 1 2 3 4 5 6 7 8 9 …
2^x: 1 2 4 8 16 32 64 128 …
a^2: 0 1 4 9 16 25 36 49 64 …
2*a^2: 0 2 8 18 32 50 72 …
我们可以发现2x里面有的数，a2和2*a^2里面都有。
加下划线的字一一对应，加粗的字一一对应。
①2 ^ x和a ^ 2, 当x为偶数时二者出现重复。
②2 ^ x和2*a ^ 2，当x为奇数时，二者出现重复。
所以不需要考虑2 ^ x的个数，直接用n减去a ^ 2和2*a^2的个数就是我们要的结果。
易知：a ^ 2的个数=sqrt(n)，2*a^2的个数=sqrt(n/2)。
那么为什么会是这样呢？给出推导过程：
n=p1 ^ e1p2 ^ e2…,则f(n)=(p1 ^ (e1+1)-1)/(p1-1))(p2^(e2+1)-1)/(p2-1))…
且(p1 ^ (e1+1)-1）/(p1-1))=p1 ^ 0+p1 ^ 1…+p1 ^ e1;
要使得f(n)为奇数，则(p1 ^ (e1+1)-1)/(p1-1)到(pn^(en+1)-1)/(pn-1)都要为奇数;
因为奇数 * 奇数=奇数，奇数 * 偶数=偶数;
1)当p=2时，2^(e+1)-1,一定为奇数;
2)当p!=2时，则p为奇数(因为p是素因子)，则当e为偶数时(p^(e+1)-1)/(p-1)为奇数。
经转化我们可以发现，26=82，211=2*322。也就是平方数和2倍的平方数。
则需要统计1到n中的平方数个数和2倍的平方数的个数，得到的为1到n中f(n)为奇数的个数。
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { int t; scanf("%d",&t); for(int kase=1;kase<=t;kase++) { LL n; scanf("%lld",&n); LL num1=(LL)sqrt((double)n); LL num2=(LL)sqrt((double)n/2.0); printf("Case %d: %lld\n",kase,n-num1-num2); } return 0; }
![[解题报告]《算法零基础100讲》(第9讲) 算术基本定理](https://ucc.alicdn.com/pic/developer-ecology/656767e7d88248e4b3c8aca2ef64b5b2.png?x-oss-process=image/resize,h_160,m_lfit)