題干：

單測試點時限: 2.0 秒

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

“他覺得一個人奮斗更輕松自在。跟沒有干勁的人在一起廝混，只會徒增壓力。”

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

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

比如在十進制下的 24 在二進制下是 11000 ，我們稱十進制下的 24 在二進制下末尾恰好有 3 個 0 。

QQ 小方一籌莫展，你能幫他解決問題嗎？

輸入

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

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

輸出

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

樣例

Input

2 1 10 2 3 1 100 2 3

Output

1 6

提示

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

解題報告：

然后作差就行了。

但是注意這題要處理高精度問題。處理方法有兩個，要么變乘法為除法，要么換范圍更大的整數(shù)（選稍微比longlong大一點的就可以了）

AC代碼1：

#include<cstdio> #include<assert.h> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define fi first #define se second #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e2 + 6; const ll INF = 0x3f3f; ll l,r,k,m; unsigned ll tmp; unsigned ll cal(unsigned ll x) {unsigned ll res = 0;res = x / tmp;if(tmp * k <= x && tmp*k >= 0) res -= x/(tmp*k) ;return res; } int main() {int t,n;cin>>t;while(t--) {scanf("%lld%lld%lld%lld",&l,&r,&k,&m);tmp = 1;int flag = 1;for(int i = 1; i<=m; i++) {tmp *= k;if(tmp > r || tmp < 0) {flag = 0; break;}}if(!flag) {printf("0\n");continue;}printf("%lld\n",cal(r) - cal(l-1));} return 0 ;}

AC代碼2：

#include<bits/stdc++.h> #define ll long long using namespace std; int get(ll x,int k) {int res=0;while(x){res++;x/=k;}return res; } int main() {int T,k,m;scanf("%d",&T);while(T--){ll l,r;scanf("%lld%lld%d%d",&l,&r,&k,&m);int tmp=get(r,k);if(tmp<=m){puts("0");continue;}ll x=pow(1ll*k,m);ll ans=r/x-(l-1)/x;if(r/x>=k)ans-=(r/(x*k)-(l-1)/(x*k));printf("%lld\n",ans);} }

或者使用Python：

T=int(input()) for i in range(T):l,r,k,m=map(int,input().split())now=k**ma=now*kprint((r//now-(l-1)//now)-(r//a-(l-1)//a))

?

總結(jié)

以上是生活随笔為你收集整理的【EOJ Monthly 2019.02 - D】进制转换（思维，取模，高精度大数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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