任意門(mén)：https://acm.ecnu.edu.cn/contest/140/problem/D/

D. 進(jìn)制轉(zhuǎn)換

單測(cè)試點(diǎn)時(shí)限:?2.0 秒

內(nèi)存限制:?256 MB

“他覺(jué)得一個(gè)人奮斗更輕松自在。跟沒(méi)有干勁的人在一起廝混，只會(huì)徒增壓力。”

QQ 小方?jīng)Q定一個(gè)人研究研究進(jìn)制轉(zhuǎn)換。

很快，QQ 小方就遇到問(wèn)題了。他現(xiàn)在想知道在十進(jìn)制范圍?[l,r]?內(nèi)有多少整數(shù)滿(mǎn)足在?k?進(jìn)制下末尾恰好有?m?個(gè)?0。

比如在十進(jìn)制下的?24?在二進(jìn)制下是?11000，我們稱(chēng)十進(jìn)制下的?24?在二進(jìn)制下末尾恰好有?3?個(gè)?0。

QQ 小方一籌莫展，你能幫他解決問(wèn)題嗎？

輸入

第一行包含一個(gè)整數(shù)?T?(1≤T≤105) 表示數(shù)據(jù)組數(shù)。

對(duì)于每組數(shù)據(jù)包含一行，四個(gè)整數(shù)?l,r,k,m?(?1≤l≤r≤1018,?2≤k,m≤100)，含義如題目所述。

輸出

對(duì)于每組數(shù)據(jù)輸出一行，包含一個(gè)整數(shù)，表示答案。

樣例

input 2 1 10 2 3 1 100 2 3 output 1 6

提示

例如，在?100?進(jìn)制下，末位是?90?的數(shù)不算作有末尾?0。

?

解題思路：

很明顯就是求 N % (K^m) == 0 且 N % ( K^m+1)? != 0;

但很明顯??N % (K^m) == 0? 的情況包括了 N % ( K^m+1)? != 0 的情況，而這種情況剛好就是 K^m?個(gè)數(shù) 滿(mǎn) K 進(jìn)位的情況，很容易判斷并且找出來(lái)。

wa 的原因在于沒(méi)有判斷無(wú)解的情況。。。。。菜哭

?

AC code：

1 #include<bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define LL long long 4 using namespace std; 5 LL L, R, K, M; 6 7 LL qpow(LL x, LL n) 8 { 9 LL res = 1; 10 while(n){ 11 if(n&1) res*=x; 12 x*=x; 13 n>>=1LL; 14 } 15 return res; 16 } 17 18 int main() 19 { 20 int T_case; 21 scanf("%d", &T_case); 22 while(T_case--){ 23 scanf("%lld %lld %lld %lld", &L, &R, &K, &M); 24 LL base = qpow(K, M); 25 LL ans = 0, tot = 0, tp; 26 if(M*log(K) > log(R)) ans = 0; 27 else{ 28 LL la = R/base, lb = L/base; 29 ans = la-(la/K) - (lb-(lb/K)); 30 if((L/base)%K != 0 && L%base == 0) ans++; 31 } 32 printf("%lld\n", ans); 33 } 34 35 return 0; 36 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ymzjj/p/10422484.html

總結(jié)

以上是生活随笔為你收集整理的EOJ Monthly 2019.2 (based on February Selection) D 进制转换 【数学 进制转换】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。