[bzoj 2005] [Noi 2010] 에너지 수집 수학 결론 (gcd)

[bzoj 2005] [Noi 2010] 에너지 채집
Time Limit: 1 Sec  Memory Limit: 256 MB
제목 연결
http://www.lydsy.com/JudgeOnline/problem.php?id=2005
Description
동 동 에는 긴 사각형 의 땅 이 있 는데 그 는 땅 에 에너지 식물 을 심 었 는데 이 식물 은 태양 빛 의 에 너 지 를 채집 할 수 있다.이 식물 들 이 에 너 지 를 채집 한 후에 동 동 동 은 하나의 에 너 지 를 모 으 는 기 계 를 사용 하여 이 식물 들 이 수집 한 에 너 지 를 한데 모 았 다.동 동의 식물 은 매우 가지런 하 게 심 었 고 모두 n 열 이 있 으 며 각 열 에 m 그루 가 있 고 식물의 가로 와 세로 간격 이 똑 같 기 때문에 모든 식물 에 대해 동 동 은 하나의 좌표 (x, y) 로 표시 할 수 있다. 그 중에서 x 의 범 위 는 1 ~ n 으로 x 열, y 의 범 위 는 1 ~ m 이 고 표 시 는 x 열 에 있 는 y 그루 이다.에너지 집합 기계 가 비교적 커서 이동 하기 가 불편 하기 때문에 동 동 은 그것 을 한 구석 에 놓 았 는데 좌 표 는 바로 (0, 0) 이다.에너지 집합 기 계 는 집합 하 는 과정 에서 일정한 에너지 손실 이 있다.만약 한 그루 의 식물 과 에너지 집합 기계 가 연 결 된 선분 에 k 그루 의 식물 이 있다 면 에너지 의 손실 은 2k + 1 이다.예 를 들 어 에너지 집합 기계 가 좌표 (2, 4) 의 식물 을 수집 할 때 연결 라인 에 식물 한 그루 (1, 2) 가 존재 하기 때문에 3 의 에너지 손실 이 발생 한다.식물 한 그루 가 에너지 집합 기계 와 연 결 된 선분 에 식물 이 없 으 면 에너지 손실 이 1 이 므 로 주의 하 세 요.지금 은 총 에너지 손실 을 계산 해 야 한다.n = 5, m = 4, 모두 20 그루 의 식물 이 있 으 며, 각 식물 에 에너지 집합 기계 가 에 너 지 를 수집 할 때 발생 하 는 에너지 손실 을 표시 했다.이 예 에서 모두 36 의 에너지 손실 이 발생 했다.
Input
한 줄 만 포함 하고 두 개의 정수 n 과 m 입 니 다.
Output
하나의 정수 만 포함 하여 모두 발생 하 는 에너지 손실 을 나타 낸다.
Sample Input

5 4

Sample Output
36
HINT
10% 의 데이터: 1 ≤ n, m ≤ 10;50% 의 데이터: 1 ≤ n, m ≤ 100;80% 의 데이터: 1 ≤ n, m ≤ 1000;90% 의 데이터: 1 ≤ n, m ≤ 10, 000;100% 의 데이터: 1 ≤ n, m ≤ 100, 000.
제목
문제 풀이: 전에 풀 었 던 어떤 문제 와 비슷 해서 분명히 내 놓 을 수 있 습 니 다. 모든 점 과 (0, 0) 사이 의 연결선 에 몇 개의 점 이 있 습 니까? 바로 gcd (x, y) 입 니 다.
폭력 을 행사 하면 80 점 을 받 을 수 있다
100 점 받 을까요?우 리 는 f [i] 로 하여 금 gcd = i 의 개 수 를 표시 하 게 합 니 다. 분명히 gcd 의 개 수 는 (n / i * m / i) i 의 배 수 를 다시 빼 면 됩 니 다.
'그리고 DP 처럼 하면 돼 요.
코드:
 

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //   

const int inf=0x3f3f3f3f;

/*

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int buf[10];

inline void write(int i) {

  int p = 0;if(i == 0) p++;

  else while(i) {buf[p++] = i % 10;i /= 10;}

  for(int j = p-1; j >=0; j--) putchar('0' + buf[j]);

  printf("
");

}

*/

//**************************************************************************************



int gcd(int x,int y)

{

    return y==0?x:gcd(y,x%y);

}

ll f[maxn];

int main()

{

    ll n,m;

    cin>>n>>m;

    if(n<m)

        swap(n,m);

    ll ans=0;

    for(ll i=n;i;i--)

    {

        f[i]=(n/i)*(m/i);

        for(ll j=2*i;j<=n;j+=i)

            f[i]-=f[j];

        ans+=f[i]*(2*i-1);

    }

    cout<<ans<<endl;

}