Fox üçün Gülüş#12239

Fox üçün Gülüş (Həll təhlili)

Tapşırığın müəllifi:	Andriy Xolod (Connect)
Hazırlayan:	Anna Yaroş (Anna_Yarosh)
İzah:	Andriy Xolod (Connect)

Həll

Qeyd edək ki, bütün $x$ ədədləri tam şəkildə $n - n mod 10$ n - n \bmod 10 ədədinə bölünməlidir. Bunu ziddiyyət yolu ilə sübut etmək olar. Əgər $n$ -dən kiçik ən böyük ədəd $n - n mod 10$ n - n \bmod 10-dan böyükdürsə, onda $n mod x$ n \bmod x həmişə $n mod 10$ n \bmod 10-dan kiçik olacaq. Əgər bu ədəd $n mod 10$ n \bmod 10-dan kiçikdirsə, onda $n mod x$ n \bmod x həmişə $n mod 10$ n \bmod 10-dan böyük olacaq. Həmçinin bütün $x$ ədədləri $n mod 10$ n \bmod 10-dan böyük olmalıdır, çünki bu halda hər zaman $n - n mod 10$ n - n \bmod 10-dan böyük və $x$ -ə tam bölünən bir $m$ ədədi tapılacaq.

Beləliklə, məsələ sadəcə $n - n mod 10$ n - n \bmod 10 ədədinin bütün bölənlərini tapmaq və onlardan $n mod 10$ n \bmod 10-dan böyük olanları artan sıra ilə çap etməkdən ibarətdir.

Həllin asimptotik mürəkkəbliyi $O (n)$ O(\sqrt{n})-dir.

#include <bits/stdc++.h>
#include <random>

using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double

#define pll pair <ll, ll>
#define pls pair <ll, string>
#define pb push_back
#define mp make_pair

const ll DIM = 2e6+7;
const ll bsize = 450;
const ll INF = 1e12;
const ll mln = 1e6+7;
const ll mod = 998244353;
const ld gold = ((1+sqrt(5))/2);

vector <ll> a;

void solve(){

    ll n;

    cin>>n;

    ll last = n%10;
    ll k = n-last;

    ll cnt = 0;
    for(ll i=1; i*i<=k; i++){

        if(k%i == 0 && i > last){
            cnt++;
            a.push_back(i);
        }
        if(k%(k/i) == 0 && k/i > last && i != k/i){
            cnt++;
            a.push_back(k/i);
        }
    }

    sort(a.begin(), a.end());

    cout<<cnt<<endl;
    for(auto to : a) cout<<to<<" ";
}

int main(){
    speed;

    int test = 1;
   //cin>>test;

    while(test--){
        solve();
        //cout << '\n';
    }

    return 0;
}

C++