 /**//*
给出mx,my,w(1<= mx,my<=10^5, 1<= w <= 10^7)
求minimal{x*y},1<=x<=mx,1<=y<=my
使得[1 x][1 y]这个区域内满足 a*b = rev(a)*rev(b)的点的个数>=w
我能想到的是
先预处理出所有rev(a),从左到右扫描x,加进新的点(即所有满足x*b = rev(x)*rev(b),1<=b<=my)
然后二分y,找出满足w的最小的y
也想到将a*b = rev(a)*rev(b)变形为 a/rev(a) = rev(b)/b,但想不下去了,
不知怎么快速获取所有满足x*b = rev(x)*rev(b)(主要是因为a/rev(a)是浮点数,不知怎么用下标存)
看了别人的,用map<double,int>就可以了 →.→
看了watashi的,是存分子分母(先用gcd约分一下) ------------------------------OMG

总体算法就是
从左到右扫描x,加入所有满足x*b = rev(x)*rev(b)的点
而满足这个条件的就是满足x/rev(x) = rev(b)/b的,由于之前已经存了mpy[(b,rev(b))]
满足上面式子点的个数就是mpy[(rev(x),x)]了
比较神奇的是,他在枚举x时,要获取满足>=w的y,不是二分y的,是通过微调的 -----------OMG
即若当前的x*y范围内的点>=w,
y--;
iw -= mpx[(rev(y),y)];
mpy[(y,rev(y))]--;
若<w,再补上去


第一次看到这样微调的,神奇丫~~~~~~~~~
y从my出发
一直保持iw>=w,微调至最接近w但>=w
整个过程,y肯定是递减的~~~
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

const long long INF = 12345678987654321LL;
const int MAXN = 100100;

pair<int,int> r[MAXN];//(i, rev(i))

 inline int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}

 inline int rev(int x) {
int r = 0;
 while(x > 0) {
r = r*10 + x % 10;
x /= 10;
}
return r;
}

 pair<int,int> inv(pair<int,int> &p) {
return make_pair(p.second, p.first);
}

 void init() {
 for (int i = 1 ; i <= 100000; i++) {
int t = rev(i);
int g = gcd(i,t);
r[i] = make_pair(i/g, t/g);
}
}

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif

init();
 for (int mx,my,w; ~scanf("%d%d%d", &mx, &my, &w);) {

map<pair<int,int>, int> mpx, mpy;
 for (int y = 1; y <= my; y++) {
mpy[r[y]]++;
}

long long X = -1, Y = -1;
long long iw = 0;
 for (long long x = 1, y = my; x <= mx; x++) {//y是从my出发的
iw += mpy[inv(r[x])];
mpx[r[x]]++;
 while(iw >= w) {
iw -= mpx[inv(r[y])];
mpy[r[y]]--;
y--;
 if(iw < w) {
y++;
mpy[r[y]]++;
iw += mpx[inv(r[y])];
break;
}
}
//一直保持着iw>=w,然后引进新的x时,尝试y--
//整个过程,y肯定是递减的~~~
 if(iw>=w && (X == -1 || x*y < X*Y) ) {
X = x;
Y = y;
}
}
 if (X == -1) {
puts("-1");
 } else {
printf("%I64d %I64d\n", X, Y);
}
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|