#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair <int, int>
#define sz(a) (int)(a.size())
#define resize(v) v.resize(unique(all(v)) - v.begin());
#define all(a) a.begin(), a.end()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
using namespace std;
void Fast_Read_Out()
{
ios_base::sync_with_stdio(0);
cin.tie(), cout.tie();
}
void Random()
{
unsigned int seed;
asm("rdtsc" : "=A" (seed));
srand(seed);
}
unsigned int Time()
{
unsigned int time = clock() / 1000.00;
return time;
}
const int inf = (1e9) + 123;
const int N = (1e7) + 1;
vector <int> v, z;
int lp[N], d[N];
vector <int> pr;
vector <pair <int, int> > per;
void Resheto()
{
for(int i = 2; i <= N - 1; i++)
{
if(lp[i] == 0)
{
lp[i] = i;
pr.pb(i);
}
for(int j = 0; j < sz(pr) && pr[j] <= lp[i] && pr[j] * i * 1ll <= N - 1; j++) lp[pr[j] * i] = pr[j];
}
}
void Prime_Multipliers(int x)
{
int del = 2;
int ans = 1;
v.clear();
while(x > 1)
{
if(d[x])
{
v.pb(x);
break;
}
while(x % del == 0) v.pb(del), x /= del;
del++;
}
}
int binpow(int a, int n)
{
if(n == 0) return 1;
if(n % 2 == 1) return binpow(a, n - 1) * a;
else
{
int b = binpow(a, n / 2);
return b * b;
}
}
main ()
{
#ifdef JUDGE
freopen("input.txt", "r", stdin);
// freopen("fast.txt", "w", stdout);
#endif
Random();
Fast_Read_Out();
int a, b;
cin >> a >> b;
Resheto();
for(int i = 0; i < sz(pr); i++) d[pr[i]]++;
long long res = 0;
if(a == 1) a++, res++;
for(int j = a; j <= b; j++)
{
if(d[j])
{
res += j - 1;
continue;
}
Prime_Multipliers(j);
per.clear();
int b1 = 1, q = v[0], n = 1, ok = 1;
for(int i = 1; i < sz(v); i++)
{
if(q != v[i])
{
if(ok) per.pb(mp(q, n + 1));
else per.pb(mp(q, n));
ok = 0;
q = v[i];
n = 2;
}
else n++;
}
per.pb(mp(q, n));
long long k = 1;
for(int i = 0; i < sz(per); i++)
{
long long up = (1 - binpow(per[i].F, per[i].S));
long long down = (1 - per[i].F);
long long sn = up / down;
k *= sn;
}
if(k > j) k -= j;
res += abs(j - k);
}
cout << res << endl;
#ifdef JUDGE
// cout << Time() << endl;
#endif
}
// Easy Peasy Lemon Squeezy Sometimes it's the very people who no one imagines anything of who do the things no one can imagine.
Compilation message
savrsen.cpp: In function 'void Prime_Multipliers(int)':
savrsen.cpp:57:6: warning: unused variable 'ans' [-Wunused-variable]
int ans = 1;
^~~
savrsen.cpp: At global scope:
savrsen.cpp:82:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main ()
^
savrsen.cpp: In function 'int main()':
savrsen.cpp:105:10: warning: unused variable 'b1' [-Wunused-variable]
int b1 = 1, q = v[0], n = 1, ok = 1;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
81376 KB |
Output is correct |
| 2 |
Correct |
191 ms |
81376 KB |
Output is correct |
| 3 |
Incorrect |
210 ms |
81440 KB |
Output isn't correct |
| 4 |
Incorrect |
189 ms |
81444 KB |
Output isn't correct |
| 5 |
Execution timed out |
3024 ms |
81444 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3034 ms |
81556 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3057 ms |
81576 KB |
Time limit exceeded |
| 8 |
Incorrect |
1366 ms |
81676 KB |
Output isn't correct |
