LightOJ1336

题目大意：

　　给你一个 n ，求出 1 到 n 中有多少个数的因数和为偶数。

解题思路：

　　可以先求出因数和为奇数的数字的个数。

　　由算术基本定理我们可以得到：N=P₁^a1P₂^a2P₃^a3 … P_n^an， σ(N) = (1+p₁+p₁²+ … +p₁^a1)(1+p₂+p₂²+ … +p₂^a2) … (1+p_n+p_n²+ … +p_n^an). 其中各个 p 均为素数。

　　我们先考虑那些因数中没有 2 的数。由于 σ(N) 为奇数，那么对于式中相乘的各项应该都是奇数，一个显而易见的事实是：除了 2 以外其他的素数均为奇数。我们随意取出一项：(1+p_i+p_i²+ … +p_i^ai)，不难发现一个结论：如果 ai 为偶数，那么这一项的和为奇数；否则为偶数。于是我们可以大胆地推测 σ(N) 中各个非2质因数的指数均为偶数，那么这些数均为平方数，我们只需去掉 1 到 n 中的所有平方数，即可去掉那些因数中没有 2 而且因数和为奇数的数。

　　如果考虑因数中有 2 的数呢？其实只需在上面求出各个平方数时顺便再乘一下 2 即可。

AC代码：

 #include<stdio.h>

 #include<math.h>

 typedef long long ll;

 int main(){

     int t;

     ll n;

     scanf("%d",&t);

     for(int j=;j<=t;j++){

         scanf("%lld",&n);

         ll ans=n;

         for(ll i=;i*i<=n;i++){

             ans--;

             if(*i*i<=n) ans--;

         }

         printf("Case %d: %lld\n",j,ans);

     }

     return ;

 }

巴特西

LightOJ1336

最新文章

热门文章