BZOJ 2705 [SDOI2012] Longge 문제풀이

2705: [SDOI2012] Longge 질문

Time Limit: 3 Sec
Memory Limit: 128 MB
Submit: 628
Solved: 402
[ Submit][ Status]

Description

롱지는 수학 성적이 매우 좋고 고난도의 수학 문제에 도전하기를 매우 좋아한다.지금 문제가 생겼다: 정수 N을 정하려면 ∑gcd(i, N)(1<=i<=N)을 구해야 한다.

Input

N의 정수

Output

구한 답안에 대한 정수.

Sample Input

Sample Output

HINT

[데이터 범위] 60%의 데이터에 대해 0

Source

round1 day1

【분석】:
∑gcd(i,N)(1<=i<=N)를 구하고 오라 함수로 참고하십시오
http://blog.csdn.net/csyzcyj/article/details/17332211 <
BZOJ 2190 [SDOI2008] 의장대 문제풀이>
【코드】:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 4294967297
int N;
long long phi(int x)
{
      long long ans=x;
      for(int i=2;i*i<=x;i++)
      {
            if(!(x%i))
            {
                  ans=ans/i*(i-1);   
                  while(x%i==0){x/=i;}
            }
      }
      if(x>1) ans=ans/x*(x-1);  
      return ans;
}
int main()
{
      //freopen("input.in","r",stdin);
	  //freopen("output.out","w",stdout); 
      scanf("%lld",&N);
      long long ans=0;
      for(int i=1;i*i<=N;i++)
      {
            if(!(N%i))
            {
                ans+=i*phi(N/i);
                if(i*i!=N)
                     ans+=(N/i)*phi(N/(N/i));
            }
      }
      printf("%lld
",ans);
	  //system("pause");
      return 0;
}

전재 설명 출처:http://blog.csdn.net/u011400953