P10246题解

**前言（忙人跳过）**  
比赛的时候本来想拿部分分，莫名其妙就对了，于是来发题解。  
**方法1（24分）**  
很容易就可以想到，先预处理出一共范围内 $k$ 的正整数次幂，然后枚举一下所有的日期。只要发现日期合并以后是 $k$ 的正整数次幂，就记录答案。  
**方法2（100分）**  
虽然日期有很多个，但是在一定范围内 $k$ 的正整数次幂只有那么几个（哪怕 $k = 2$ 的时候用低精度最多也只有 $62$ 个数），我们可以反过来看，把所有 $k$ 的正整数次幂写出来，一个一个拆分，每一次拆分都检查有没有这个拆分以后的日期不就行了。  
有了思路，那废话不多说，直接上代码吧！但是，代码里也有许多细节~~坑了我~~哦！
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LONG_LONG_MAX
#define INT_MIN LONG_LONG_MIN
int a[300005];
struct node {
	int month,day;
} ans[20005];
int cmp(node x,node y) {
	if(x.month!=y.month) {
		return x.month<y.month;
	}
	return x.day<y.day;
}
int wei(int n){//计算位数 
	int num;
	num = 0;
	while(n){
		n = n/10;
		num++;
	}
	return num;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,n,k,num,now;
	cin>>t;
	while(t--) {
		cin>>n>>k;
		num = 0;
		now = 1;//num:答案个数  now:现在要拆分的数是多少  
		int maxn;//maxn:把每一个日期合起来的位数最大是多少  
		maxn = INT_MIN;
		for(int i = 1; i<=n; i++) {
			cin>>a[i];
			maxn = max(maxn,wei(i)+wei(a[i]));//每一个月里的日期组成的最大位数就是该月编号位数+该月最大日期位数 
		}
		if(k == 1) {//如果k是1，它的所有正整数次幂都是1，日期中月和日合并最少是2位，故加上特判防止死循环  
			cout<<"0\n";
			continue;
		}
		while(wei(now)<=maxn) {//这里一定不要偷懒写wei(now)<=1e15，不然你可能会像我一样TLE的很惨 
			now = now*k;
			if(now<10) {//同理，日期中月和日合并最少是2位
				continue;
			}
			int l,r;
			l = now/10;
			r = now%10;
			//不懂的看这里：
			//12345678   9 
			for(int i = 10; l; i = i*10) {
				if(l && l<=n && r && r<=a[l]) {//坑点:日期中不能有一个是0 虽然这里l不可能是0，但是还是写上保险（c++很玄学的） 
					ans[++num].month = l;
					ans[num].day = r;
				}
				while(l%10 == 0 && l!=0) {//坑点:有时候中间有0，那么如果只移一位过去那么就会导致日期合并起来不是原数了
				//如果只移一位那么在样例第2组数据的输出里面就会多出一个1 24，实际上是1024拆出来的 
					r = r+l%10*i;
					l = l/10;
					i = i*10;//不要忘记！ 
				}
				r = r+l%10*i;
				l = l/10;//刚才是处理中间有0的情况，但是大于0的那一位没有移过去，要再移一次。 
			}
		}
		sort(ans+1,ans+num+1,cmp);//答案不一定有序，要排序  
		cout<<num<<"\n";
		for(int i = 1; i<=num; i++) {
			cout<<ans[i].month<<" "<<ans[i].day<<"\n";
		}
	}
	return 0;
}
```