oj.uz

답안 #466931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466931 2021-08-21T03:27:36 Z KDisabledA Savrsen (COCI17_savrsen) C++14
120 / 120
 506 ms 81300 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;
int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
}
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;
    scanf("%d %d",&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]);
    printf("%lld",res);
}
 
//-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:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 0; j < pr.size() && pr[j] <= lp[i] && 1ll*i*pr[j] <= n; ++j)
      |                        ~~^~~~~~~~~~~
savrsen.cpp: In function 'int main()':
savrsen.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %d",&l,&r);
      |     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 4 ms 1236 KB Output is correct
4 Correct 477 ms 81244 KB Output is correct
5 Correct 486 ms 81300 KB Output is correct
6 Correct 506 ms 81284 KB Output is correct
7 Correct 448 ms 75088 KB Output is correct
8 Correct 102 ms 21056 KB Output is correct