题意描述：
设 (rev(i)) 表示把 (i) 的每一位翻转之后所得到的数。
如果 $a imes b = rev(a) imes rev(b) $ , 则称数对 ((a,b)) 是合法的。
(f(n,m)) 表示：(ileq n,jleq m), 且数对 ((i,j)) 是合法的数对的个数。
现在给你三个数 (x_{max},y_{max},w)， 让你求一组 ((x,y)) 满足：(f(x,y)geq w) 且 (xleq x_{max},yleq y_{max}) ，(x imes y) 最小,无解则输出 (-1)。
数据范围： (x_{max},y_{max}leq 10^5, wleq 10^7) 。
solution：
( map) + 双指针。
首先我们考虑一个问题就是怎么求出 (f(n,m)) 。
我们把 (a imes b = rev(a) imes rev(b)) 变形为：({aover rev(a)} = {rev(b)over b})。
然后可以先开个 (map) 存一下 (aover rev(a)) 出现的次数， 然后在枚举一下 (b) ，那么 (b) 对 (f(n,m)) 的贡献就是 (rev(b)over b) 的出现次数。
在能求出来 (f(n,m)) 之后，我们这道题就很好做了。
我们可以先扫一遍求出 (f(x_{max},y_{max})) ,无解的情况就是 (f(x_{max},y_{max}) > w)
至于有解的情况，我们维护两个指针 (l,r) 表示 当 (x=l) 时，符合条件的 (y) 最小为 (r) 。
同时维护一个 变量 (cnt)， 表示当前 (f(l,r)) 的值。
不难发现，随着 (l) 的递增， (r) 一定是单调递减的。
所以我们可以拿双指针维护一下，同时再开两个 (map) 用来统计 (aover rev(a)) 和 (rev(b)over b) 出现的次数。
当 (l,r) 指针移动的时候, 用 (map) 就可以直接维护出指针移动之后 (cnt) 的值 （类似于莫队的指针移动）。
复杂度： (O(nlogn))
code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int maxx,maxy,w,l,r,ans,ansl,ansr,cnt,sum;
map<double,int> t1,t2;
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int rev(int x)
{
int res = 0;
while(x)
{
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
int main()
{
maxx = read(); maxy = read(); w = read(); ans = 1e10;
for(int i = 1; i <= maxx; i++) t1[1.0*i/rev(i)]++;
for(int i = 1; i <= maxy; i++) sum += t1[1.0*rev(i)/i];//求f(maxx,maxy)
if(sum < w) printf("%d
",-1);//无解的情况
else
{
l = maxx, r = 0;
while(l && r <= maxy)
{
while(cnt < w && r <= maxy)
{
r++;
t2[1.0*rev(r)/r]++;
cnt += t1[1.0*rev(r)/r];//r指针对cnt的贡献
}
if(cnt >= w && r*l < ans)
{
ans = r*l;
ansl = l; ansr = r;
}
cnt -= t2[1.0*l/rev(l)];//l向左移对cnt的贡献
t1[1.0*l/rev(l)]--;
l--;
}
printf("%d %d
",ansl,ansr);
}
return 0;
}