Untitled
unknown
plain_text
10 months ago
2.9 kB
6
Indexable
#include<bits/stdc++.h> #define ll long long using namespace std; const int M = 1e6 + 500; const ll dlt = 10739; ll nchildren[M]; ll inf = 1e6 - 1; set <int> beauty; bool mark[M] = {}; ll mod(ll n){ n = n % dlt; if(n < 0) n += dlt; return n; } ll father(ll a){ for(ll i = 2; i * i <= a; i++) if(!(a % i)) return a / i; return 1; } ll num_divisors(int a){ int ans = 1; for(int i = 2; i*i <= a; i++){ int cnt = 0; while(!(a % i)){ a /= i; cnt ++; } ans *= (cnt + 1); } if(a != 1) ans *= 2; return ans; } void num_children(int n){ for(int i = 2; i <= n; i++){ nchildren[father(i)]++; } } ll i_wana_be_a_spy(ll n){ ll ans = (1e12) * nchildren[n]; ll u = father(n); if(num_divisors(u) >= 3 and num_divisors(u) <= 5) ans += (1e6) * nchildren[u]; else ans += (1e6) * inf; u = father(u); if(num_divisors(u) >= 3 and num_divisors(u) <= 5) ans += nchildren[u]; else ans += inf; return ans; } ll who_am_i(ll n){ const ll a = 1e12; return n / a; } ll who_is_myfather(ll n){ ll a = 1e12; n = n % a; a = 1e6; n /= a; return n; } ll who_is_mygrandfather(ll n){ ll a = 1e6; return n % a; } void make(int n){ for(int i = 2; i <= n; i++){ if(num_divisors(i) >= 3 and num_divisors(i) <= 5) beauty.insert(i); } for(auto u : beauty){ mark[father(u)] = 1; } } int main(){ ios::sync_with_stdio(0); //cin.tie(0); ll n, k; cin >> n >> k; multiset <ll> vec; num_children(n); make(n); cout << beauty.size() << endl; for(auto u : beauty){ if(!mark[u]) vec.insert(i_wana_be_a_spy(u)); } ll sum = 0; ll x = 0, y = 0, help = 0; cout << vec.size() << endl; while(who_am_i(*vec.begin()) == 0){ x++; ll u = who_is_myfather(*vec.begin()); ll v = who_is_mygrandfather(*vec.begin()); vec.erase(vec.begin()); if(u != inf) vec.insert((u - 1) * 1e12 + v * 1e6 + inf); } cout << x << endl; cout << vec.size() << endl; for(int i = 1; i <= k; i++){ if(!vec.empty()){ ll neww = *vec.begin(); neww -= 1e12; vec.erase(vec.begin()); vec.insert(neww); help++; while(who_am_i(*vec.begin()) == 0){ x++; y += help; help = 0; ll u = who_is_myfather(*vec.begin()); ll v = who_is_mygrandfather(*vec.begin()); vec.erase(vec.begin()); if(u != inf) vec.insert((u - 1) * (1e12) + v * (1e6) + inf); } } ll A = mod(x * y); sum = mod(sum + mod(A * A)); } cout << sum << endl; return 0; }
Editor is loading...
Leave a Comment