Untitled

 avatar
AlirezaZare3
c_cpp
17 days ago
1.6 kB
1
Indexable
Never
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef long long ll;

inline ll pw(ll base, ll e);

const ll dlt = 10607, N = 1e3 +10, M = 60;
ll cnt[N];

ll _sum(ll &a, ll b){a = a + b; if(a > dlt){a -= dlt;}}

bool check_prime(int n){
    for(int i = 2; i*i <= n; i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;
}


void sub1(){
    for(ll i = 1; i < N; i++){
        for(ll j = i + 1; j < N ;j++){
            if(__gcd(i,j) == 1){
                cnt[j]++;
            }
        }
    }

    ll sum = 0;
    for(ll i = 1; i < N; i++){
        if(cnt[i] == M){
            _sum(sum,(i*i)%dlt);
        }
    }

    cout << sum%dlt << endl;
}



void sub2(){
    vector<int>good_P;
    for(int i = 1; i <= 50; i++){
        int a = pw(2, i) + 1;
        if(check_prime(a)){
            good_P.push_back(a);
        }
    }

    int sum = 0;
    for(int i = 0; i < pw(2, good_P.size()); i++){
        vector<int>vec; vec.clear();
        for(int j = 0; j < good_P.size(); j++){
            if(i>>j & 1){
                vec.push_back(good_P[j]);
            }
        }


        int d = 1, ans = 1;
        for(int k : vec){
            ans *= k;
            d *= (k-1);
        }

        ans *= (pw(2, 50) / d)*2;
        sum += (ans%dlt)*(ans%dlt)%dlt;
    }

    cout << sum%dlt << endl;
}




signed main(){
    sub1();
    sub2();
    return 0;
}


inline ll pw(ll base, ll e){
    if(e < 0){return 0;}
    ll ans= 1;
    while(e){
        if(e&1){
            ans = 1ll*ans*base;
        }
        base = 1ll*base*base;
        e >>= 1;
    }
    return ans;
}
Leave a Comment