UVA 725 Division

原题Vjudge

题目大意

给你个\(N\)
判断有没有两个整数满足\(\frac{A}{B} = N\)，并且\(A和B\)的各位数字刚好构成\(0\sim9\)的一个排列

解题思路

这题乍一看挺难的，但是范围很小(\(2\le N \le 79\))，那我们就可以着手写暴力
将上述等式进行变形，可以得到\(A = NB\)，而\(N\)是固定的，所以我们只需要算出\(B\)
就可以得到\(A\)了。对于每对\(A和B\)我们还需要判断是否构成排列
这个简单，将每位的数字做一个桶计数，然后看看是不是从\(0\sim9\)都有就行了

枚举细节

关于这个枚举，我们可以得到\(B\)是四位数，而且\(A\)是五位数，那么可以得到
对于任意的\(B\)合法，有\(1234\le B\le 98765 \div n\)，
所以可以这样枚举我们的B

for (int B = 1234; B * n <= 98765; B ++ ) 

代码实现

#include <iostream>
#include <cstring>

using namespace std;

int st[15], n, kase;

bool isPerm(int B, int A) 
{
    memset(st, 0, sizeof st);
    if (A > 98765) return false ;
    
    for (int i = 0; i < 5; i ++ ) 
    {
        st[A % 10] ++, st[B % 10] ++ ;
        A /= 10, B /= 10;
    }
    for (int i = 0; i < 10; i ++ )
        if (st[i] != 1) return false ;
    return true ;
}

int main()
{
    while (scanf("%d", &n), n) 
    {
        if (kase ++ > 0) printf("\n"); // 恶心的输出
        
        bool soul = false; //是否有解
        for (int B = 1234; B * n <= 98765; B ++ ) 
        {
            if (isPerm(B, n * B)) //能否构成排列
            {
                printf("%05d / %05d = %d\n", n * B, B, n);
                soul = true ; //有解
            }
        }
        if (!soul) printf("There are no solutions for %d.\n",n);
    }
    
    return 0;
}

Accepted!!