LightOJ 13361336 - Sigma Function （找规律 + 唯一分解定理）

本文主要是介绍LightOJ 13361336 - Sigma Function （找规律 + 唯一分解定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

 

题意：

求 1—n 中，有多少个数的因子和是偶数。

题解：

下面这个题解可能到后面就看不懂了，我对其做一下解释：
1.只有奇数乘奇数是奇数，所以下面的思路最后是找到所有因子和为奇数的个数。
2.
如果p[i]==2,则p[i]^0 + p[i]^1 +.....+ p[i]^e[i]为奇数；
如果p[i]!=2,则p[i]一定为奇数（因为p肯定为素数）且p[i]^e[i]也为奇数（数乘奇数是奇数）。因为只有奇数+偶数=奇数，我们需要做到两两组合（奇数+奇数对于偶数），剩下一个奇数（奇数+偶数=奇数），所以e[i]要保证为偶数。
3.
e[i]为偶数，所以一定可以化简为某个数的平方，所以只要找出n以内的平方数就能够找出所有的满足第二个条件的个数，再加上第一个函数，有一个质因子是2，所以在平方数乘以二倍即可即2x^2.

思路来自：https://blog.csdn.net/qq_15714857/article/details/48831341

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)
#define kuaidian ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;     
int main()
{ll n;int t;scanf("%d",&t);int cas=0;while(t--){scanf("%lld",&n);ll a1=sqrt(n);ll a2=sqrt(double(n/2));printf("Case %d: %lld\n",++cas,n-a1-a2);}return 0;
}

 

这篇关于LightOJ 13361336 - Sigma Function （找规律 + 唯一分解定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---