程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> URAL 1057 Amount of Degrees(數位統計)

URAL 1057 Amount of Degrees(數位統計)

日期:2017/1/3 15:17:31      編輯:關於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<

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved