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
6
Sample Output
15
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
