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.zzzyk.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
*/

补充：软件开发 , C++ ,

Uva 11395 - Sigma Function 规律 对数

Uva 11395 - Sigma Function 规律对数