#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
#define forw(i,a,b) for (ll i=a;i<=b;i++)
#define forb(i,a,b) for (ll i=a;i>=b;i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9;
const int base=31;
const int tx[4]={0,0,1,-1};
const int ty[4]={1,-1,0,1};
// custom
const ll maxN=1e7+2;
const int tx1[4]={2,2,1,-1};
const int ty1[4]={-1,1,2,2};
/////
ll a, b,ans;
vector <int> prime; //prime
vector <int> spf; // smallest prime factor
void sieve()
{
spf.assign(maxN+5,2);
spf[1]=1;
prime.pb(2);
for(int i=3;i<=maxN;i+=2)
{
if (spf[i]==2)
prime.pb(spf[i]=i);
for(int j=0;j<prime.size() && prime[j]*i<=maxN && prime[j]<=spf[i];j++)
spf[i*prime[j]]=prime[j];
}
}
ll power(ll a,ll n)
{
ll ans=1;
while (n>0)
{
if (n&1) ans=ans*a;
a=a*a;
n>>=1;
}
return ans;
}
ll get(int x)
{
ll ans=1;
while (x>1)
{
int p=spf[x];
int res=0;
while (x%p==0)
{
x/=p;
res++;
}
ans*=(power(p,res+1)-1)/(p-1);
}
return ans;
}
void solve()
{
sieve();
cin>>a>>b;
forw(i,a,b)
ans+=abs(2*i-get(i));
cout<<ans<<endl;
}
int main()
{
fast;
//freopen("HHH.inp","r",stdin);
//freopen("HHH.out","w",stdout);
ll t=1; //cin>>t;
while (t--) solve();
return 0;
}
Compilation message
savrsen.cpp: In function 'void sieve()':
savrsen.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int j=0;j<prime.size() && prime[j]*i<=maxN && prime[j]<=spf[i];j++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
43672 KB |
Output is correct |
| 2 |
Correct |
94 ms |
43632 KB |
Output is correct |
| 3 |
Correct |
96 ms |
43652 KB |
Output is correct |
| 4 |
Correct |
84 ms |
43628 KB |
Output is correct |
| 5 |
Correct |
1033 ms |
43672 KB |
Output is correct |
| 6 |
Correct |
1124 ms |
43692 KB |
Output is correct |
| 7 |
Correct |
1034 ms |
43652 KB |
Output is correct |
| 8 |
Correct |
345 ms |
43668 KB |
Output is correct |
