首页 > 代码库 > ACDream - Xor pairs

ACDream - Xor pairs

先上题目:

Xor pairs

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

long long ans = 0;
for(int i = 1; i <= n; i ++)
    for(int j = i + 1; j <= n; j ++)
       for(int k = j + 1; k <= n; k ++)
           if((i ^ j ^ k) == 0) ans ++;

 

Input

约10000组数据,每组数据一行n (1 <= n <= 10^9)

Output

对于每组数据,输出一行,ans

Sample Input

101112

Sample Output

101317

  第一眼看输入只有一个数字,然后就有输出,这有很大几率是找规律。
  打表以后发现好像规律还不是很明显,将相邻的两项相减,然后就找到规律了:0,1,0,1,2,3,0,1,2,3,4,5,6,7,0,``````
  然后就是构造函数了,思路是先求出距离输入的n最近的2的次幂求和的那个幂数,然后求出每一个以2的次幂-1为终结的等差数列的和,求出以后再加上多出来的那一部分等差数列,就可以得到的数了。中间可能还需要一点小的调整。

上代码:

 1 /* 2 * this code is made by sineatos 3 * Problem: 1183 4 * Verdict: Accepted 5 * Submission Date: 2014-07-31 14:59:31 6 * Time: 8MS 7 * Memory: 1088KB 8 */ 9 #include <cstdio>10 #include <cstring>11 #include <algorithm>12 #define MAX 10000213 #define ll long long14 using namespace std;15  16 int main()17 {18     ll n,i,c,r;19     while(~scanf("%lld",&n))20     {21         if(n<2) printf("0\n");22         else if(n==3) printf("1\n");23         else24         {25             ll sum=0;26             c=0;27             for(i=1; (c+i)<n; i<<=1)28             {29                 c+=i;30                 sum+=i*(i-1)/2;31             }32             r=n-c;33             sum+=(1+(r-1))*(r-1)/2;34             printf("%lld\n",sum);35         }36     }37  38     return 0;39 }
/*Xor pairs*/