新生训练

生蚝作为ACM@WUT的顶尖成员，早早地拿牌退役了。心善的Messi不忍心让他闲着，于是派他去训练新生。
这天训练的内容是数学，生蚝：“我们从比较简单的数学说起，比如约分，约分其实就是分子分母有相同的部分就消去，直到无法消去为止。”这里生蚝其实说的是消去相同的非 $1$ 因数，结果表述不清楚。
于是他就看到了某个新生写了下面这个式子。

生蚝血压差点爆炸，刀都要拔出来了，突然发现，这个式子好像结果是对的啊？
不得不说这是一次教学事故，生蚝为了挽回颜面，决定研究一下什么时候会使得上面这种错误的解法得到正确答案。

给定分子的取值范围 $[L_1,R_1]$ ，分母的取值范围 $[L_2,R_2]$ ，分子分母都是正整数，问经过错误的约分计算后有哪些分数答案可能与该分数的约分最简式完全一样（ $01$ 与 $1$ 不一样）。
错误的计算：

在分子和分母的数位中各找一位，使得这两个数位上的数字相同，若找不到或已经不存在数位则退出；
删去这两个数位，返回第一步

特别注意：按照上面的方式计算出来不一定是一个正确的分式形式，如2/2还可以继续计算，最后只剩/，显然这与最简式1/1不同。

第一行一个整数 $n$ ，表示所求的分数的个数；
第二行到第 $n+1$ 行，每行输出"x/y=a/b"（不含引号），其中"x/y"是约分前，"a/b"是约分的结果。

为了使答案便于判断，输出结果以x/y为第一关键字，x为第二关键字排序后输出，即x/y小的排前面，x/y相等时x小的排前面。

#include<bits/stdc++.h> using namespace std; int l1,l2,r1,r2,a[1010],b[1010],n=0,m=0; struct node { int a,b,c,d; }o[1010000]; int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } inline bool cmp(node a,node b) { double x=(double)a.a/a.b; double y=(double)b.a/b.b; if(fabs(x-y)<1e-10) return a.a<b.a; else return x<y; } int main() { scanf("%d%d%d%d",&l1,&r1,&l2,&r2); for(int i=l1;i<=r1;i++) { for(int j=l2;j<=r2;j++) { int x=i,y=j,k1=0,k2=0; while(x>0) { a[++k1]=x%10; x/=10; } while(y>0) { b[++k2]=y%10; y/=10; } for(int p=1;p<=k1;p++) { for(int q=1;q<=k2;q++) { if(a[p]==b[q]) { a[p]=-1; b[q]=-1; } } } int h=0,l=0; for(int p=k1;p>0;p--) { if(a[p]!=-1) h=h*10+a[p]; } for(int q=k2;q>0;q--) { if(b[q]!=-1) l=l*10+b[q]; } if(l==0||h==0) continue; x=i,y=j; x/=gcd(i,j),y/=gcd(i,j); if(h==x&&l==y){ o[m++]={i,j,x,y}; } }} sort(o,o+m,cmp); printf("%d\n",m); for(int i=0;i<m;i++) { printf("%d/%d=%d/%d\n",o[i].a,o[i].b,o[i].c,o[i].d); } }

详情