算法题

题目传送门

蒟蒻的第一篇博客

大致思路

记x右边添加了k个0,那么就有:

$$y=10^k*x $$

$$n=x+y=x*(10^k+1) $$

又有$11≤n≤10^{18}$,于是可以枚举$10^k$,最多枚举18次
当n能被$10^k+1$整除时
答案就是 $n/(10^k+1)$,最后排序一下输出即可

Code

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lll __int128
#define Mio_qh signed
#define el '\n'
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pq priority_queue
const int MOD = 998244353;
const int N = 100721;

int fastpow(int base, int exp) {
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = (base*result)%MOD;
        exp >>= 1;
        base = (base*base)%MOD;
    }
    return result;
}
int hx[8]={1,1,-1,-1,2,-2,2,-2};
int hy[8]={2,-2,2,-2,1,1,-1,-1};

void print(lll x) {
    if(x==0) cout<<0<<el;
    else {
        string ans="";
        while(x!=0) {
            int t=x%10;
            ans=to_string(t)+ans;
            x=x/10;
        }
        cout<<ans<<el;
    }
}

void solve() {
    int n;
    cin>>n;
    int power=1;
    vector<int> ans;
    while (true){
        power*=10;
        if (power+1>n) break;
        if (n%(power+1)==0) ans.pb(n/(power+1));
    }
    if (ans.empty()) {
        cout<<0<<el;
        return;
    }
    sort(all(ans));
    cout<<ans.size()<<el;
    for (auto i:ans) cout<<i<<" ";
    cout<<el;
}


Mio_qh main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
}

说些什么吧！

waline