（本题取 $n=9$）
【思路】题目描述得有些模糊，要求我们找到两个十位数 $a,b$（$a \lt b$），使得 $a$ 的十位数和 $b$ 的个位数相等，同时使得 $\dfrac{a}{b}$ 与 $a,b$ 分别删去相同位数之后的商相等。
由于有两个数位相等，因此我们只需要枚举三个数位，这样就可以在 $\mathcal O(n^3)$ 枚举出所有的情况。约分需要用到 $\gcd$，因此最终时间复杂度为 $\mathcal O(n^3 \log n)$：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<stdio.h>
struct fraction
{
int n,d;
}ans;
int gcd(int a,int b)
{
while(b)
{
int t=b;
b=a%b;
a=t;
}
return a;
}
int main()
{
ans.n=ans.d=1;
for(int i=1;i<=9;++i)
{
for(int j=i+1;j<=9;++j)
{
for(int k=i+1;k<=9;++k)
{
int n=i*10+j,d=j*10+k;
if(n*k==d*i)
{
ans.n*=n;
ans.d*=d;
}
}
}
}
printf("%d",ans.d/gcd(ans.n,ans.d));
return 0;
}
|