oj.uz

Submission #1101138

# Submission time Handle Problem Language Result Execution time Memory
1101138 2024-10-15T15:24:09 Z InvMOD Savrsen (COCI17_savrsen) C++14
120 / 120
 431 ms 39596 KB 
#include <bits/stdc++.h>
using namespace std;

#define gcd __gcd
#define fi first
#define se second
#define lcm(a, b) a*b/gcd(a,b)
#define sz(v) v.size()
#define pb push_back
#define el "\n"
#define pi pair<ll , ll>
#define all(v) (v).begin(), (v).end()
#define rev(v) reverse(all(v))
#define compact(v) v.erase(unique(all(v)), end(v))
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T &a, T b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T &a, T b){if(a > b) return a = b, true; return false;}

const int N = 1e7+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


int minPrime[N];

void sieve(){
    for(int i = 2; i*i < N; i++){
        if(!minPrime[i]){
            for(int j = i*i; j < N; j+=i){
                if(!minPrime[j]) minPrime[j] = i;
            }
        }
    }
    for(int i = 2; i < N; i++){
        if(!minPrime[i]) minPrime[i] = i;
    }
    return;
}

ll mul(ll a, ll b){return (a*b);}

ll binpow(ll a, ll b){
    ll res = 1;
    for(; b > 0; b >>= 1, a = mul(a, a)){
        if(b&1)res = mul(res, a);
    }
    return res;
}

ll factor(int x){
    ll prv = minPrime[x];
    ll cnt = 0, res = 1, cx = x;
    if(x == 1) return 1;
    while(x > 1){
        if(prv != minPrime[x]){
            res *= (binpow(prv, cnt+1)-1)/ (prv - 1);
            prv = minPrime[x];
            cnt = 0;
        }
        cnt++;
        x /= minPrime[x];
    }
    res *= (binpow(prv, cnt+1)-1)/ (prv-1);
    res -= cx;
    return abs(cx - res);
}

void solve()
{
    int a,b; cin >> a >> b;
    ll res = 0;
    sieve();
    for(int i = a; i <= b; i++){
        ll fact = factor(i);
        res += fact;
    }
    cout << res <<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message

savrsen.cpp: In function 'int main()':
savrsen.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
savrsen.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 39568 KB Output is correct
2 Correct 112 ms 39496 KB Output is correct
3 Correct 107 ms 39476 KB Output is correct
4 Correct 115 ms 39456 KB Output is correct
5 Correct 421 ms 39596 KB Output is correct
6 Correct 431 ms 39492 KB Output is correct
7 Correct 425 ms 39596 KB Output is correct
8 Correct 176 ms 39388 KB Output is correct