LightOJ 1336 Sigma Function 算数基本定理

题目大意：f(n)为n的因子和,给出 n 求 1~n 中f(n)为偶数的个数.

题目思路:算数基本定理:

n=p1^e1*p2^e1 …… pn^en （p为素数）；

f(n)=（1+p1+p1^2+p^3……+p^e1）*(1+p2+p2^2……+p2^e2)……*(1+pn+pn^2……+pn^en)。

偶数个个奇数相乘仍为奇数，奇数个奇数相乘则为偶数，为了使f(n)为奇数，那么多项式中的每一项都应为奇数。

对于每个多项式内：偶数个奇数相加为偶数，奇数个奇数相加为奇数，为了使多项式为奇数，那么e应为偶数（因为前面还要加1）。

我们知道：

若 n=p1^e1*p2^e1 …… pn^en；

那么 n^2=（p1^e1*p2^e1 …… pn^en）^2 =p1^2e1*p2^2e1 …… pn^2en。

2为唯一一个偶素数，且p=2的项一定为奇数。

所以我们则需要统计1到n中的平方数个数和2倍的平方数的个数，得到的为1到n中f(n)为奇数的个数。

#include<cstdio>

#include<stdio.h>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

#define MAX 1005

using namespace std;

int main()

{

    int cnt=,T;

    long long n,sum;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld",&n);

        sum=;

        for(long long i=;i*i<=n;i++)

        {

            sum++;

            if(*i*i <= n)

                sum++;

        }

        printf("Case %d: %lld\n",cnt++,n-sum);

    }

}

巴特西

LightOJ 1336 Sigma Function 算数基本定理

最新文章

热门文章