Submission #466953

#TimeUsernameProblemLanguageResultExecution timeMemory
466953XBoRickieSavrsen (COCI17_savrsen)C++11
120 / 120
620 ms117688 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...