Pagini recente » Cod sursa (job #1949792) | Cod sursa (job #1599524) | Cod sursa (job #2410326) | Cod sursa (job #930804) | Cod sursa (job #2501548)
#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 = 1e3 ;
bool sieve[MV + 5] ;
int primeNumbers[10005] ;
std::vector<long long> getPrimeDivisors(long long B) {
std::vector<long long> ret ;
for (long long divisor(2) ; divisor * divisor <= B ; ++ divisor) {
if (B % divisor == 0) {
ret.push_back(divisor) ;
for ( ; B % divisor == 0 ; B /= divisor) ;
}
}
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) ;
i64 ans = 0 ;
A -- ;
B -- ;
for (int i = 1 ; i <= A ; ++ i) {
ans += (B - solve(B, i)) ;
}
fprintf(out, "%lld\n", ans) ;
}