Home PAT 1160 Forever
Post
Cancel

PAT 1160 Forever

Link

思路:

首先要明确的是, 个位数一定是 9, 否则 A+1 一定与 A 互质 (因为必定一个是奇数, 一个是偶数).

既然已经规定了位数必须是 K, 那么就可以枚举从低位到高位的第一个不是 9 的位是哪一位. 假设从个位开始有连续的 S 个 9, 那么就有 n=m-9*S+1.

此时如果有 gcd(n,m)>2, 那么就说明和为 m 且末尾有连续的 S 个 9 的数 A 是可行的. 既然和为 m, 那么减去末尾的 9, 剩下的就是高 K-S 位的数之和. 于是问题转化为: 一个 K-S 位的数, 其各位数字之和等于一个已知数 m-9*S, 一共有多少个满足条件的数?

这个问题就是使用 DFS 来解决的.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pp;
const int N=110;
int n,k,m;
bool primes[N];
vector<pp>ans;
string mstr;
inline int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
inline int sum(int e){
    int cnt=0;
    while(e){
        cnt+=e%10;
        e/=10;
    }
    return cnt;
}
inline bool isPrime(int a){
    if(a<=2) return false;
    for(int i=2;i*i<=a;++i)
        if(a%i==0) return false;
    return true;
}
void DFS(int rest,int cur){
    mstr.push_back(cur+'0');
    if(mstr.size()<k){
        for(int i=0;i<=9;++i)
            if((k-mstr.size())*9>=rest)
                DFS(rest-i,i);
    }else if(rest==0){
        int a=stoi(mstr),b=sum(a+1);
        if(isPrime(gcd(b,m)))
            ans.emplace_back(b,a);
    }
    mstr.pop_back();
}
int main() {
    scanf("%d",&n);
    for(int c=1;c<=n;++c){
        scanf("%d%d",&k,&m);
        printf("Case %d\n",c);
        ans.clear();
        for(int i=1;i<=9;++i)
            DFS(m-i,i);
        if(ans.empty()) puts("No Solution");
        else{
            sort(ans.begin(),ans.end(),[](pp &a,pp &b){
                if(a.x!=b.x) return a.x<b.x;
                return a.y<b.y;
            });
            for(auto &j:ans){
                printf("%d %d\n",j.x,j.y);
            }
        }
    }
    return 0;
}

PS: 看到了一位大佬写的代码, 代码风格很优雅, 非常值得学习: 链接🔗

This post is licensed under CC BY 4.0 by the author.