oj.uz

Submission #466926

# Submission time Handle Problem Language Result Execution time Memory
466926 2021-08-21T03:22:08 Z KDisabledA Savrsen (COCI17_savrsen) C++14
120 / 120
 490 ms 81440 KB 
#include<bits/stdc++.h>
#include<ext/numeric>
#define fastIO                  ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
#define FOR(i, j, k, in)		for (int i = (j); i < (k); i += (in))
#define FORW(i, j, k, in)		for (int i = (j); i <= (k); i += (in))
#define RFOR(i, j, k, in)		for (int i = (j); i >= (k); i -= (in))
#define RFORW(i, j, k, in)		for (int i = (j); i > (k); i -= (in))
#define sz(arr)                 ((int)(arr).size())
#define pb                      push_back
#define fi						first
#define se						second
#define mp						make_pair

using namespace std;
using namespace __gnu_cxx;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef pair<pii,int> piii;
typedef vector<pii> vii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;

const int inf=INT_MAX-(13*7);
const float PI=acos(-1);
const ll linf=LLONG_MAX-(13ll*7ll);
const int N=1e7+7;
vi pr;
int l,r;
void sieve(int n = sqrt(1e9)) {
    int lp[n + 12] = {};
    FORW(i, 2, n, 1) {
        if (lp[i] == 0) lp[i] = i, pr.pb(i);
        for(int j = 0; j < pr.size() && pr[j] <= lp[i] && 1ll*i*pr[j] <= n; ++j)
            lp[i * pr[j]] = pr[j];
    }
}
int ans[N];
int main(){
    /*#ifndef ONLINE_JUDGE
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    #endif // ONLINE_JUDGE*/
    fastIO;
    cin>>l>>r;
    sieve(r);
    FORW(i,1,r,1) ans[i]=1;
    for(auto x:pr){
        ll s=1;
        for(ll i = x; i <= r; i *= x) {
            for(ll j = i; j <= r; j += i) {
                ans[j] /= s;
                ans[j] *= (s + i);
            }
            s += i;
        }
    }
    ll res = 0;
    FORW(i, l, r, 1) res += abs(2 * i - ans[i]);
    cout << res << endl;
}

//-T nghi la t khong the de mat 1 nguoi ban tot nhu m dau =)))
//

Compilation message

savrsen.cpp: In function 'void sieve(int)':
savrsen.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0; j < pr.size() && pr[j] <= lp[i] && 1ll*i*pr[j] <= n; ++j)
      |                        ~~^~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 4 ms 1228 KB Output is correct
4 Correct 475 ms 81440 KB Output is correct
5 Correct 490 ms 81276 KB Output is correct
6 Correct 486 ms 81324 KB Output is correct
7 Correct 455 ms 75056 KB Output is correct
8 Correct 104 ms 21072 KB Output is correct