Pagini recente » Cod sursa (job #746779) | Cod sursa (job #2263268) | Cod sursa (job #2634189) | Cod sursa (job #2065587) | Cod sursa (job #592805)
Cod sursa(job #592805)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1000005;
int i , j , n , m , phi[maxn];
int list[maxn][9];
ll ans;
int count (int x)
{
int i;
int ans = 0;
for( i = 1 ; i < (1 << list[x][0]) ; ++i ) {
int p = 1 , cnt = 0;
for( j = 0 ; (1 << j) <= i ; ++j )
if ( i & (1 << j) )
cnt++ , p *= list[x][j + 1];
if ( cnt & 1 )
ans += m / p;
else
ans -= m / p;
}
return m - ans;
}
int main()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%d %d",&n,&m);
n-- , m--;
if ( n < m )
swap(n , m);
for( i = 1 ; i <= n ; ++i )
phi[i] = i;
for( i = 2 ; i <= n ; ++i ) {
if ( phi[i] == i )
for( j = i ; j <= n ; j += i )
phi[j] /= i , phi[j] *= (i - 1) , list[j][++list[j][0]] = i;
if ( i <= m )
ans += 1LL * 2 * phi[i];
else
ans += count(i);
}
printf("%lld\n",ans + 1);
return 0;
}