Untitled
AlirezaZare3
c_cpp
a year ago
1.6 kB
4
Indexable
#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; }
Editor is loading...
Leave a Comment