白駿14072は何回ですか.

4680 ワード
数学 アルゴリズム#アルゴリズム# テキストリンク

質問リンク


https://www.acmicpc.net/problem/1407

質問する



に答える


範囲は1<=A<=B<=10^15なので、いちいち追加することはできません.
だから私はどんなルールがあるか調べてみました.
1
2
3
4
5
6
7
8
9
ここで2で割らない数は
=>ceil(9/2)=5個存在します.
残りの数量について
2
4
6
8
4割り切れない数.
=>ceil(4/2)=>2個.
再対剰余
4
8
8で割らない数.
=>ceil(2/2)=>1個.
8
16で割らない数.
=>ceil(1/2)=>1個.
したがって、
  • は、1〜9の各数の最大2の反復二乗数を加算した値が1 x 5+2 x 2+4 x 1+8 x 1=17である.
    • 1からNに含まれる各数について、最大の2を加えた繰返し二乗数のすべての値を返す関数をF(N)と呼ぶ.
    A〜Bの範囲では、F(B)−F(A−1)を用いて回答を得ることができる.

    試行錯誤

  • の段階的な征服に挑戦しようとしたが、複雑になって諦めてしまった.
  • 型変換のため、ceil関数は何度も書き間違えた.

    • コード#コード#

    #include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll a, b;
ll solve(ll a) {
	ll ans = 0, temp = 1;
	while (a != 0) {
		if (a % 2 != 0) ans += ((a / 2) + 1)*temp;
		else ans += (a / 2)*temp;
		a /= 2;
		temp *= 2;
	}
	return ans;
}

int main(void) {
	cin >> a >> b;
	cout << solve(b) - solve(a - 1);
}

    ポスト


    考えが複雑すぎる!
    ES 8323 CODEC駆動
    linux gpio_keysの上位検出コード