P1176奇怪的数列
背景
一天。学军数学小组的成员遇到了一个奇怪的数列,正巧信息小组的你碰到了他们。
于是他们把这个数列展示给你……
描写叙述
这个数列是这种:
0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31……
先细致研究一下这个数列的规律。
如今他们请你编写一个程序,要求找出数n在此数列中的位置序号k。
格式
输入格式
输入数据仅仅有一行,为数 n (n<=2^31-1)
输出格式
输出数据仅仅有一行,为数k。
限制
时限:1s
来源
From chnlkw,wlfish
a(n) = if n<2 then n else 2*m + (n mod 2 + m mod 2) mod 2, with m=a(floor(n/2)).
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <vector> #include <cstdio> #include <cctype> #include <string> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define pb push_back #define mp make_pair #define fillchar(a, x) memset(a, x, sizeof(a)) #define copy(a, b) memcpy(a, b, sizeof(a)) #define S_queue<P> priority_queue<P, vector<P>,greater<P> > typedef long long LL; typedef pair<int, int > PII; typedef unsigned long long uLL; template<typename T> void print(T* p, T* q, string Gap = " "){int d = p < q ? 1 : -1;while(p != q){cout << *p;p += d;if(p != q) cout << Gap; }cout << endl;} template<typename T> void print(const T &a, string bes = "") {int len = bes.length();if(len >= 2)cout << bes[0] << a << bes[1] << endl;else cout << a << endl;} const int INF = 0x3f3f3f3f; const int MAXM = 1e6 + 5; const int MAXN = 1e4 + 5; uLL fun(uLL x){ if(x < 2) return x; else{ uLL m = fun(floor(x / 2)); return 2 * m + (x % 2 + m % 2) % 2; } } int main(){ uLL n; //freopen("D://out.txt","w",stdout); scanf("%I64d", &n); print(fun(n) + 1); }