Cod sursa(job #592802)

Utilizator klamathixMihai Calancea klamathix Data 30 mai 2011 19:45:16
Problema Mins Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long 
const int maxn = 1000005;
int i , j , n , m , phi[maxn];
vector <int> list[maxn];
ll ans;

ll count (int x)
{
	int i;
	ll ans = 0;
	
	for( i = 1 ; i < (1 << list[x].size()) ; ++i ) {
		int p = 1 , cnt = 0;
		
		for( j = 0 ; (1 << j) <= i ; ++j )			
			if ( i & (1 << j) )
				cnt++ , p *= list[x][j];
			
			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].push_back(i);
		if ( i <= m )
			ans += 1LL * 2 * phi[i];
		else
			ans += count(i);
	}
	
	printf("%lld\n",ans + 1);
	
return 0;
}