Pagini recente » Clasament mpractice1 | Cod sursa (job #381070) | Cod sursa (job #1961942) | Cod sursa (job #1838604) | Cod sursa (job #2501546)
#include <bits/stdc++.h>
#define int long long
FILE *in = fopen("mins.in", "r"), *out = fopen("mins.out", "w") ;
typedef long long i64 ;
const int MV = 45e3 ;
bool sieve[MV + 5] ;
int primeNumbers[20005] ;
void SIEVE() {
int index(0) ;
for (i64 i = 2 ; i <= MV ; ++ i) {
if (sieve[i] == 0) {
primeNumbers[index ++] = (i) ;
for (i64 j = i * i ; j <= MV ; j += i) {
sieve[j] = 1 ;
}
}
}
}
std::vector<i64> getPrimeDivisors(i64 B) {
std::vector<i64> ret ;
for (int i = 0 ; primeNumbers[i] * primeNumbers[i] <= B ; ++ i) {
if (B % primeNumbers[i] == 0) {
ret.push_back(primeNumbers[i]) ;
for ( ; B % primeNumbers[i] == 0 ; B /= primeNumbers[i]) ;
}
}
if (B > 1) {
ret.push_back(B) ;
}
return ret ;
}
i64 compute(i64 state, i64 divisors, std::vector<i64> primeDivisors, i64 limit) {
i64 numberSubSets = __builtin_popcount(state) ;
i64 setCoef = ((numberSubSets % 2) ? 1 : -1) ;
i64 currentDivisor(1) ;
for (int i = 0 ; i < divisors ; ++ i) {
if (state & (1 << i)) {
currentDivisor *= primeDivisors[i] ;
}
}
return (limit / currentDivisor) * setCoef ;
}
i64 solve(i64 A, i64 B) {
std::vector<i64> primeDivisors = getPrimeDivisors(B) ;
i64 divisors(primeDivisors.size()) ;
i64 ret(0) ;
for (i64 state(1) ; state < (1 << divisors) ; ++ state) {
ret += compute(state, divisors, primeDivisors, A) ;
}
return ret ;
}
signed main() {
int tests ;
i64 A, B ;
fscanf(in, "%lld %lld", &A, &B) ;
SIEVE() ;
i64 ans = 0 ;
A -- ;
B -- ;
for (int i = 1 ; i <= A ; ++ i) {
ans += (B - solve(B, i)) ;
}
fprintf(out, "%lld\n", ans) ;
}