LightOJ 1336 Sigma Function(唯一分解定理)

题目链接：http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1336

 

题目大意：求1~n中，约数和为偶数的数字个数

 

题目思路：根据唯一分解定理，约数和为f(x)= (1+p1+p1^2+p1^3+...+p1^a1)*(1+p2+p2^2+...+p2^a2)*...*(1+pn+pn^2+...+pn^an);

只有奇数乘以奇数才能还是奇数，所以每个括号内的值都应该是奇数

所以考虑奇数的情况，用n减去就行

质数只有2是偶数，所以2所在的那一项除了1都是偶数，整个项一定为奇数，所以2^x一定符合要求

而对于不是2的质数，当他们有偶数个时，整个项为奇数，而奇数个时，整个项为偶数

所以就需要找出所有除了2的质因数为偶数个的情况

而当他们为偶数时，就一定是一个平方数，如果他们还有2,2的数量为奇数时，就是2*一个平方数，否则就是平方数本身

2^x一定属于平方数或2*平方数

所以找出n内所有平方数和2*平方数即可

除暴力外，还可以直接通过公式o1得到，平方数个数就直接开根号即可，而2*平方数个数就直接对/2结果开根号即可

 

以下是代码：

暴力：

#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define rep(i,a,b) for(ll i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) #define ll long long const int MAXN = 1e7+5; const int MOD =1e9+7; int main(){ int t; ll n; scanf("%d",&t); rep(_,1,t){ scanf("%lld",&n); ll ans=n; rep(i,1,sqrt(n)){ if(i*i<=n)ans--; if(2*i*i<=n)ans--; } printf("Case %d: %lld\n",_,ans); } return 0; }

公式：

#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) #define ll long long const int MAXN = 1e7+5; const int MOD =1e9+7; int main(){ int t; ll n; scanf("%d",&t); rep(_,1,t){ scanf("%lld",&n); ll ans=(ll)sqrt(n)+(ll)sqrt(n/2); printf("Case %d: %lld\n",_,n-ans); } return 0; }