有趣的数学题

• UVA12716
• UVA11582

UVA12716 GCD XOR

题解

参考
这题用到2个结论
a ^ b = c -----> a ^ c = b
a ^ b = gcd( a, b )----->a - b = gcd( a, b ),打表发现。。
设a - b = gcd( a, b ) = c, 枚举c。然后判断 a ^ c == a - c即可

代码

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 30000000;

int cnt[ maxn + 10 ], sum[ maxn + 10 ];
int n, Cas, T;

void pre()
{
    for( int i = 1; i <= maxn / 2; i ++ )
    {
        for( int j = i + i; j <= maxn; j += i )
        {
            if( ( j ^ i ) == j - i ) cnt[ j ] ++;
        }
    }
    for( int i = 1; i <= maxn; i ++ ) sum[ i ] = sum[ i - 1 ] + cnt[ i ];
}

int main()
{
    memset( cnt, 0, sizeof( cnt ) );
    memset( sum, 0, sizeof( sum ) );
    pre();
    Cas = 0;
    scanf( "%d", &T );
    while( T -- )
    {
        scanf( "%d", &n );
        printf( "Case %d: %d\n", ++Cas, sum[ n ] );
    }
    return 0;
}