
任意门:https://acm.ecnu.edu.cn/contest/140/problem/D/
D. 进制转换
单测试点时限: 2.0 秒
内存限制: 256 MB
“他觉得一个人奋斗更轻松自在。跟没有干劲的人在一起厮混,只会徒增压力。”
QQ 小方决定一个人研究研究进制转换。
很快,QQ 小方就遇到问题了。他现在想知道在十进制范围 [l,r] 内有多少整数满足在 k 进制下末尾恰好有 m 个 0。
比如在十进制下的 24 在二进制下是 11000,我们称十进制下的 24 在二进制下末尾恰好有 3 个 0。
QQ 小方一筹莫展,你能帮他解决问题吗?
输入
第一行包含一个整数 T (1≤T≤105) 表示数据组数。
对于每组数据包含一行,四个整数 l,r,k,m ( 1≤l≤r≤1018, 2≤k,m≤100),含义如题目所述。
输出
对于每组数据输出一行,包含一个整数,表示答案。
样例
input
2
1 10 2 3
1 100 2 3
output
1
6
提示
例如,在 100 进制下,末位是 90 的数不算作有末尾 0。
解题思路:
很明显就是求 N % (Km) == 0 且 N % ( Km+1) != 0;
但很明显 N % (Km) == 0 的情况包括了 N % ( Km+1) != 0 的情况,而这种情况刚好就是 Km 个数 满 K 进位的情况,很容易判断并且找出来。
wa 的原因在于没有判断无解的情况。。。。。菜哭
AC code:
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
LL L, R, K, M; LL qpow(LL x, LL n)
{
LL res = ;
while(n){
if(n&) res*=x;
x*=x;
n>>=1LL;
}
return res;
} int main()
{
int T_case;
scanf("%d", &T_case);
while(T_case--){
scanf("%lld %lld %lld %lld", &L, &R, &K, &M);
LL base = qpow(K, M);
LL ans = , tot = , tp;
if(M*log(K) > log(R)) ans = ;
else{
LL la = R/base, lb = L/base;
ans = la-(la/K) - (lb-(lb/K));
if((L/base)%K != && L%base == ) ans++;
}
printf("%lld\n", ans);
} return ;
}