程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> URAL 1057 Amount of Degrees（數位統計）

URAL 1057 Amount of Degrees（數位統計）

編輯：關於C++

求給定區間[X,Y]中滿足下列條件的整數個數：這個數恰好等於K 個互不相等的B的整
數次冪之和。

思路：對於二進制來說（圖片摘自劉聰的淺談數位類統計問題論文）

現在推廣到b進制

因為對於b進制的每一位，我們只需要討論這一位是否是一，所以我們可以把這個數轉換為一個等價的二進制數，

方法是將這個數從左到右第一位不是零或一的位變為1，並把其右邊的所有位置一，求出這個二進制數。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define LL long long
#define pii (pair)
//#pragma comment(linker, /STACK:1024000000,1024000000)
using namespace std;

//const int maxn = 100 + 5;
//const int INF = 0x3f3f3f3f;
LL f[40][40];
int x, y, k, b;

void init() {
    f[0][0] = 1;
    for(int i = 1; i <= 31; i++) {
        f[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            f[i][j] = f[i-1][j] + f[i-1][j-1];
        }
    }
}

int cal(int x, int k) {
    int tot = 0, ans = 0;
    for(int i = 31; i > 0; i--) {
        if((1< k) break;
            x ^= (1< v;
    while(x) {
        v.push_back(x%b);
        x /= b;
    }
    int sz = v.size();
    for(int i = sz-1; i >= 0; i--) {
        if(v[i]==1 || !v[i]) {
            ans += (v[i]==0 ? 0 : (1<