oj.uz

Submission #466953

# Submission time Handle Problem Language Result Execution time Memory
466953 2021-08-21T03:56:55 Z XBoRickie Savrsen (COCI17_savrsen) C++11
120 / 120
 620 ms 117688 KB 
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
using namespace std;
const int MOD=1e9+7,N=1e7;
const ll INF=1e18;
int A,B;
int prime[N+5];
ll f[N+5];
ll x,y,z,t;
ll ans;
int main(){
	for (int i=2;i*i<=N;i++)
	if (prime[i]==0)
	for (int j=i*i;j<=N;j+=i)
	if (prime[j]==0)
	prime[j]=i;
	cin>>A>>B;
	f[1]=1;
	for (int i=2;i<=B;i++){
		if (prime[i]==0){
			f[i]=i+1;
			continue;
		}
		x=i;
		y=0;
		z=1;
		t=1;
		while (x%prime[i]==0){
			t*=prime[i];
			z+=t;
			y++;
			x/=prime[i];
		}
		f[i]=f[x]*z;
	}
	for (int i=A;i<=B;i++)ans+=abs(f[i]-2*i);
	cout<<ans<<endl;
    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 39424 KB Output is correct
2 Correct 148 ms 39416 KB Output is correct
3 Correct 156 ms 40176 KB Output is correct
4 Correct 565 ms 117616 KB Output is correct
5 Correct 596 ms 117688 KB Output is correct
6 Correct 620 ms 117660 KB Output is correct
7 Correct 555 ms 111536 KB Output is correct
8 Correct 263 ms 59220 KB Output is correct