Uva 11395 - Sigma Function （算术基本定理）

Uva 11395 - Sigma Function （算术基本定理）

从单个数字看，它的因子和与素因子的指数相关。由

奇数+奇数=奇数

奇数*偶数=偶数

我们得到结论，如果因子和是偶数，那么至少有一个

是奇数.

即对于数字N的判断：

#include #include #include using namespace std;typedef long long LL;const int N=1e6+10;bool vis[N];vector prim;int cnt=0;void getprim(){ for(int i=2;i2&&(pow&1)){ tag=1; break; } } } if(tag==0) puts("奇数"); else puts("偶数"); return 0;}

但是本题的N数据很大，遍历判断显然不行。

只能从宏观上看，试着由N直接判断问题的解。

反过来想，什么时候因子和是奇数呢？

由前面的分析，当除2外的所有的素因子的指数都是偶数的时候，因子和就是奇数。

”除2外的所有的素因子的指数都是偶数“ 意味着它是一个平方数，或者2*平方数. 当只有2这个素因子时，它无论怎样都是奇数，不过它也可以归结于上面的两种情况。

所以，写成这样：

code：

#include #include #include using namespace std;typedef long long LL;int main(){ int T,ca=1; LL n; cin>>T; while(T--){ scanf("%lld",&n); LL p1=(LL)sqrt(1.0*n); LL p2=(LL)sqrt(n/2.0); printf("Case %d: %lld\n",ca++,n-p1-p2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。