beats

3509. [NOIP 2013 시 뮬 레이 션 11.5B 팀] 재수 없 는 C (beats)  (File IO): input:beats.in output:beats.out
Time Limits: 
1000 ms  Memory Limits: 
262144 KB  Detailed Limits  
Goto ProblemSet
Description
G 군 은 최근 섬나라 애니메이션 '엔 젤' 에 푹 빠 졌 다. Beats, 그녀 는 더 패기 넘 치 는 엔 젤 을 그 리 려 고 Beats 로고, 다음 과 같은 방법 을 생각 했 습 니 다.
(0, 0) 부터 (n, 1) 까지 그리고 (n, 1) 부터 (2 * n, - 1) 까지 그리고 (3 * n, 2) 까지 그리고 (4 * n, - 2) 까지 유추 하면 매번 (n, (- 1) ^ (i + 1) * i) 의 벡터 를 그 려 서 모두 n 개의 벡터 를 그린다.현재 G 는 작은 C 에 게 이 도형 이 몇 칸 을 통과 하 는 지 구 하려 고 한다.
C 군 은 수학 수업 을 열심히 듣 고 계주 에서 RP 의 폭발 로 계주 가 잘못 전 달 된 것 과 같은 나 쁜 일이 발생 하고 싶 어 하기 때문에 이 문 제 는 당신 에 게 맡 기 겠 습 니 다.G 군 은 너 마저 해결 하지 못 하면 RP 도 다 빨 아들 이 라 고 한다.
Input
파일 에 하나의 행동 만 정수 n 을 입력 하 십시오.
Output
출력 파일 에 서 는 입 었 던 칸 수 를 표시 하 는 행동 하나 뿐 입 니 다.
Sample Input

4

Sample Output

9

Data Constraint
20% 의 데이터 에 만족: n < = 100;
40% 의 데이터 에 만족: n < = 10 ^ 5;
60% 의 데이터 에 만족: n < = 10 ^ 7;
100% 의 데이터 에 만족: n < = 10 ^ 10.

#include
#include
#include
using namespace std;
long long a,b,d,ans;
long long fai(long long);
int main()
{
	freopen("beats.in","r",stdin);
	freopen("beats.out","w",stdout);
	scanf("%lld",&a);
	for (b=1;b<=trunc(sqrt(a));b++)
	{
		if (a%b==0)
		{
			d=b;
			ans=ans+d*fai(a/d);
			if (d!=a/d) 
			{
				d=a/b;
				ans=ans+d*fai(a/d);
			}
		}
	}
	ans++;
	printf("%lld",ans);
	return 0;
}
long long fai(long long x)
{
	int i;
	long long t;
	t=x;
	i=2;
	while (x>1) 
	{
		if (x%i==0) 
        {
			t=(t-t/i);
			while (x%i==0) 
    		{
				x=x/i;
			}
		}
		i++;
	}
	return t;
}