글 읽기 - 혹시 반례를 알 수 있을까요?

yhw7979 5년 전 0

오일러 파이함수를 이용해서 프로그램을 짰는데

예제도 맞고 오일러 파이함수의 값에 대한 이미지를 보고 테스트를 했는데 계속 맞아서

제출했는데 틀렸다고 나오네요. 어디가 틀린걸까요?

#include <iostream>
#include <map>
#include <cmath>

using namespace std;

map<int, int> smallNumbers; //소인수들(소인수, 소인수의 제곱횟수)

void Decomposition(int n) {
	int small = 2; //소인수 계산용
	while (n > 1) {
		if (n%small==0) { 
			smallNumbers[small]++; //해당 소인수 나온 횟수 1 증가
			n /= small;
		}
		else {
			small++; //현재 나누려는 수로는 더이상 나뉘지 않기 때문에 다음 수로 나누기 시도
		}
	}
}

int main(void) {
	while (1) {
		int num;
		int result = 1; //1은 항상 들어감

		cin >> num;
		if(num==0){
			return 0;
		}

		Decomposition(num); //입력받은 수에 대해서 소인수분해 진행

		for (map<int, int>::iterator iter = smallNumbers.begin(); iter != smallNumbers.end(); iter++) {
			result *= (pow(iter->first, iter->second) - pow(iter->first, iter->second - 1));
		}
		cout << result << "\n";
		smallNumbers.clear(); //재사용을 위해 소인수 저장한 것들 삭제
	}
}

roonm813 4년 전 1

문제 조건이 오일러 함수랑 약간 달라요.

euler_phi(1) = 1 이지만, 해당 문제에서는

1이 주어지면 0이 출력되어야합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

혹시 반례를 알 수 있을까요?

yhw7979 5년 전 0

roonm813 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말