日付変わった・・・

とりあえず今回もログだけ。

ナニコレ

nの最大の奇数の約数を返す関数f(n)がある。Nが与えられたときf(1)+f(2)+...+f(N)を求めよ。

今回も自力で解けなかった…
コメントアウトは普通のTLEコードからDPやり、配列でかすぎてsegmentation faultだして、さらに改良してたら答え自体合わなくなってしまったコード。

で、コメントアウトしてないやつが答え。なんでこうなるのかは数学的な証明が要。

class OddDivisors {
   public:
   /*int f(int n) {
   	for (int i=n-1; i>=0; i-=2) {
   		if (n%i==0) return i;
   	}
   	return -1;
   }

   long long findSum(int N)
  {
	long long sum = 0;
	int harf = (int)(N/2), tmp;
	cout << harf << endl;
	vector<long long> dp(harf);
	fill(dp.begin(), dp.end(), -1);
	for (int i=0; i<harf; i++) {
		if (dp[i] == -1) {
			tmp = (i+1)*2;
			dp[i] = f(tmp);
			for (int j=i*2+1; j<harf; j *= 2 + 1) dp[j] = dp[i];
		}
	}
	for (int i=1; i<=N; i+=2) sum += i;
	for (int i=0; i<harf; i++) sum += dp[i];
	return sum;
  }*/
  long long sum(long long n) {
  	return n*(n+1);
  }
  long long findSum(int N) {
  	long long r = 0;
  	while (N) {
  		r += sum(N)/2 -sum(N/2);
  		N /= 2;
  	}
  	return r;
  }
};