Uva 11395 - Sigma Function 規律 對數

[cpp] 
/*
*  規律:通過打表後發現，在n的范圍內，只有2^x 以及 平方數 和 平方數的2倍符合要求。
*    即：2^1, 2^2,...   1*1, 2*2,...    2*1*1, 2*2*2, 2*3*3... 等等，故只要去重就可以了
*  url:　http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2390
*  stratege: 規律，對數
*  Author: Johnsondu
*/ 
 
#include <iostream>  www.2cto.com
#include <cmath> 
#include <cstdio> 
#include <cstring> 
 
using namespace std; 
 
#define LL long long  
LL n, t1, t2, t3, t4, t5, t6 ; 
 
int main () 
{ 
    int tcase, cas = 1 ; 
    scanf ("%d", &tcase) ; 
    while (tcase --) 
    { 
        scanf ("%lld", &n) ; 
        if (n == 1) 
        { 
            printf ("Case %d: 0\n", cas++) ; 
            continue ; 
        } 
        t1 = (LL)sqrt (n*1.0) ;             //一共有t1^2 < n, 故有t1 個 
        t2 = (LL)(log(n*1.0) / log(2.0)) ;  // 2^t2 內， 有t2個 
        t3 = ((LL)(log(n*1.0) / log(2.0)) - 1) / 2 + 1 ;  // 2*x*x與2^t2中，與2^3, 2^7,...，重復 
        t4 = (LL)sqrt (n/2.0) ;  // 2*x*x一共有t4個 
        t5 = (LL) (log(t1*1.0)/log(2.0)) ;  //t1中x*x 與 2^t2重復的有t5個 
         
        printf ("Case %d: %lld\n", cas++, n - (t1 - t5 + t2 + t4 - t3)) ; 
    } 
    return 0 ; 
} 
 
/*
打表的代碼：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
#define LL long long 
#define MAXN 33000
 
int p[MAXN] ;
bool isPrime[MAXN];
int prilen, a, b ;
 
void getPrime ()
{
    int i ;
    for (i = 0; i < MAXN; i ++)
    {
        isPrime[i] = true ;
    }
    for (i = 4; i < MAXN; i += 2)
        isPrime[i] = false ;
    p[0] = 2 ;
    prilen = 1 ;
    for (i = 3; i < MAXN; i += 2)
    {
        if (isPrime[i])
        {
            int tmp = 2 * i ;
            p[prilen ++] = i ;
            while (tmp < MAXN)
            {
                isPrime[tmp] = false ;
                tmp += i ;
            }
        }
    }
}
 
int get (int n)
{
    int ans = 1 ;
    int t = n ;
    for (int i = 0; p[i]*p[i] <= t; i ++)
    {
        if (t % p[i] == 0)
        {
            int num = 0 ;
            while (t % p[i] == 0)
            {
                num ++ ;
                t/=p[i] ;
            }
            ans = ans * ((int)pow(p[i]*1.0, num+1.0) - 1) / (p[i]-1) ;
        }
    }
    if (t > 1)
        ans = ans * ((int)pow(t*1.0, 2.0)-1)/(t-1) ;
    return ans ;
}
 
int main ()
{
    getPrime () ;
    //int ans = 0 ;
    for (int i = 1; i <= 1000; i ++)
    {
        //printf ("%d -- %d\n", i, get(i)) ;
        if (get(i) % 2 != 0)
            printf ("%d --- %d\n", i, get(i)) ;
    }
    return 0 ;
}
 
 
1 --- 1
2 --- 3
4 --- 7
8 --- 15
9 --- 13
16 --- 31
18 --- 39
25 --- 31
32 --- 63
36 --- 91
49 --- 57
50 --- 93
64 --- 127
72 --- 195
81 --- 121
98 --- 171
100 --- 217
121 --- 133
128 --- 255
144 --- 403
162 --- 363
169 --- 183
196 --- 399
200 --- 465
225 --- 403
242 --- 399
256 --- 511
288 --- 819
289 --- 307
324 --- 847
338 --- 549
361 --- 381
392 --- 855
400 --- 961
441 --- 741
450 --- 1209
484 --- 931
512 --- 1023
529 --- 553
576 --- 1651
578 --- 921
625 --- 781
648 --- 1815
676 --- 1281
722 --- 1143
729 --- 1093
784 --- 1767
800 --- 1953
841 --- 871
882 --- 2223
900 --- 2821
961 --- 993
968 --- 1995
*/