Untitled

mail@pastecode.io avatar
unknown
plain_text
25 days ago
1.5 kB
5
Indexable
Never
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 1e6 + 500;
const ll dlt = 10289;
ll nchildren[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)]++;
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll n, k;
    cin >> n >> k;
    vector <ll> vec;
    num_children(n);
    for(ll i = 1; i <= n; i++){
        if(num_divisors(i) == 2){
            vec.push_back(nchildren[i]);
        }
    }
    sort(vec.begin(), vec.end());
    ll sum = 0;
    ll x = 0, y = 0, help = 0;
    ll j = 0;
    while(vec[j] == 0){
        j++;
        x++;
    }
    for(int i = 1; i <= k; i++){
        if(j >= vec.size())
            break;
        vec[j]--;
        help++;
        while(j < vec.size() and vec[j] == 0){
            j++;
            x++;
            y += help;
            help = 0;
        }
        x = mod(x);  y = mod(y);
        ll A = mod(x * y);
        sum = mod(sum + A * A);
    }
    cout << sum << endl;
    return 0;
}
Leave a Comment