글 읽기 - 오일러파이함수 시간초과...

leeym95 4년 전 0

이렇게하면 O(sqrt(n))의 시간복잡도아닌가요?

시간초과 나는데 뭐가 문제인가요 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <cmath>
#include <cstring>
#include <stack>
#include <string>
#include <queue>
#include <map>
#include <cstdio>
#pragma warning(disable:4996)
#define ll long long
#define pii pair<int, int>
#define MOD 1000000007
using namespace std;

ll n;
ll solve(ll n) {
	double res = n;
	for (int i = 2; i*i <= n; i++)
	{
		if (n % i == 0) {
			while (n % i == 0)
			{
				n /= i;
			}
			res *= (1.0 - (1.0 / (double) i));
		}
	}
	if (n != 1) res *= (1.0 - (1.0 / (double) n));
	return (ll) res;
}
int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	cout << solve(n);
	return 0;
}

gunwookim 4년 전 2

for문을 돌때 i*i 는 n이 10^12 일때 터지게 int형 범위를 벗어나게 됩니다. 그래서 long long 으로 고쳐야 합니다

leeym95 4년 전 0

감사합니다!

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

문제

문제

출처

ICPC

오일러파이함수 시간초과...

leeym95 4년 전 0

gunwookim 4년 전 2

leeym95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말