NC21885. 进制的交集
描述
输入描述
首先输入一个T，表示T组案例（T<=100000），每组案例首先输入一行两个数A,B，表示两个进制2<=A,B<=10，然后输入两行，每行两个在相应进制下的整数，分别代表该进制下L1，R1，L2，R2。
这四个整数的每个整数都满足最多18位，也就是这四个整数的每个整数变成字符串之后的长度<=18
输出描述
对于每组案例，输出答案表示有多少数字字面相同。
示例1
输入:
1 3 10 1 12 2 10
输出:
2
说明:
3进制下的2（其值等于10下的2）与10进制下的2字面相同。C++14(g++5.4) 解法, 执行用时: 126ms, 内存消耗: 1384K, 提交时间: 2020-06-10 10:07:49
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LL long long
using namespace std;
int n,m,v[20];LL l1,l2,r1,r2;
I LL Get(LL x)
{
if(x<0) return 0;RI t=0;W(x) v[++t]=x%10,x/=10;
LL ans=0;for(RI i=t,f=0;i;--i) v[i]>=n&&(f=1),(ans*=n)+=(f?n-1:v[i]);return ans+1;
}
int main()
{
RI Tt;scanf("%d",&Tt);W(Tt--)
scanf("%d%d",&n,&m),n=min(n,m),scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2),
printf("%lld\n",Get(min(r1,r2))-Get(min(l1-1,r2))-Get(min(r1,l2-1))+Get(min(l1-1,l2-1)));
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 125ms, 内存消耗: 5860K, 提交时间: 2018-12-29 08:45:49
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a,b;
int l1,r1,l2,r2;
int num[20],len;
int ask(int n1,int n2){
int n=min(n1,n2);if(n<0) return 0; int a1=0,ok=0;
for(len=0;n;num[++len]=n%10,n/=10);
for(int i=len;i;i--)
ok|=(a-1<num[i]),a1=a1*a+(ok ? a-1 : min(num[i],a-1));
return a1+1;
}
signed main(){
scanf("%lld",&T);while(T--) {
scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&l1,&r1,&l2,&r2);a=min(a,b);
printf("%lld\n",ask(r1,r2)-ask(l1-1,r2)-ask(r1,l2-1)+ask(l1-1,l2-1));
}
}