project euler 169

题目链接：https://projecteuler.net/problem=169

参考题解：http://tieba.baidu.com/p/2738022069

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define rep(i, a, b) for(int i=(a); i<(b); i++)

#define sz(x) (int)x.size()

#define de(x) cout<< #x<<" = "<<x<<endl

#define dd(x) cout<< #x<<" = "<<x<<" "

typedef __int128 ll;

typedef pair<int, int> pii;

typedef vector<int> vi;

map<ll, ll> vis;

ll solve(ll n) {

	if(n<0) return 0;

	if(n==0) return 1;

	if(vis.count(n)) return vis[n];

	if(n&1) return vis[n]=solve(n/2);

	return vis[n]=solve(n/2)+solve(n/2-1);

}

void print(ll x) {

	vi ans;

	while(x) {

		ans.pb(x%10);

		x/=10;

	}

	reverse(ans.begin(), ans.end());

	rep(i,0,sz(ans)) printf("%d",ans[i]);puts("");

}

int main() {

	ll x=1e12;

	ll n=x*x*10;

	print(n);

	ll ans=solve(n);

	print(ans);

    return 0;

}