글 읽기 - 틀렸습니다가 나옵니다

djdhad 3년 전 0

기본적으로 10^12 이하는 sqrt(n)으로 해결하고,

그 이상은 폴라드 로 알고리즘 돌리고

factor를 다 구한 다음에 오일러 phi 함수로 마무리 하는 방식으로 하고있습니다

물론 알고리즘에 들어가기 전에 밀러-라빈 판정법으로 프라임인지 먼저 확인한 다음에요.

분명 제 생각엔 맞다고 생각하는데 틀렸습니다가 나와버립니다...

안되는 예시가 뭔지도 모르니까 답답합니다

도와주세요 고수님들 ㅠㅠㅠㅠㅠ

#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool isPrime[1000001]; vector<ll> prime; ll expo[1000001];
ll ans = 1; vector<ll> x;
void check(ll n); void rho(ll n);
ll cnt = 0;

void SOE(ll n){
   for(ll i=0; i<(ll)sqrt(n)+1; i++) isPrime[i] = true;

   for(ll i=2; i<(ll)sqrt(n)+1; i++){
      if(isPrime[i]==true) {
         prime.push_back(i);
         for(ll j=i*2; j<(ll)sqrt(n)+1; j+=i) isPrime[j] = false;
      }
   }
}

void phi(ll n){
   for(ll i=0; i<prime.size(); i++){
      if(n== 1) break;
      while(n%prime[i]==0){
         expo[i]++;
         n = n/prime[i];
      }
   }
   if(n!=1) {
      ans *= n-1;
   }
}
void rho(ll n){
   x.clear(); 
   ll a = rand();
   x.push_back(a);
    
   if(n%2 == 0) {
      check(2);
      check(n/2);
   }
   else{
   for(int i=1; i<=n; i++){
      x.push_back(((x[i-1]%n)*(x[i-1]%n)+a)%n);
      ll k = abs((x[i]%n) - (x[i/2]%n))%n;
      ll d = __gcd(k,n);
      cnt++;
       
      if(d==n) return rho(n);

      else if(d>1){
         check(d);
         check(n/d);
         break;
      }
   }
   }
   return;
}
ll add(ll n, ll k, ll mod){
   n = n%mod;
   k = k%mod;
   ll temp = 0;
   while(k){
      if(k%2) temp = (temp+n)%mod;
      n = (n+n)%mod;
      k = k/2;
   }
   return temp;
}

ll power(ll n, ll k, ll mod){
   n = n%mod;
   ll temp = 1;
   while(k!=0){
      if(k%2 == 1) temp = add(temp, n,mod);
      k = k/2;
      n = add(n, n, mod);
   }
   return temp;
}

bool mr(ll n, ll a){

   ll d = n-1;
   while(d%2 == 0){
      if(power(a,d,n) == n-1) return true;
      d = d/2;
   }
   ll temp = power(a,d,n);

   if(temp == 1 || temp == n-1) return true;
   return false;
}

void check(ll n){
   if(n<= 1000000000000) return phi(n);
   else {
      for(ll a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
         if(mr(n, a) == false) return rho(n);
      }
      ans *= n-1;
   }
}

int main() {

   cin.tie(NULL);
   ios_base::sync_with_stdio(false); //Standard Setting

   ll n;
   cin >> n;

   SOE(1000000000000);
    
   for(ll i=0; i<prime.size(); i++){
      if(expo[i]>=1) {
         ans *= pow(prime[i],expo[i])-pow(prime[i],expo[i]-1);
      }
   }
   cout << ans << '\n';
}

WeissBlume 3년 전 0

123456789123456789

djdhad 3년 전 1

56052908050383360 맞나요?

djdhad 3년 전 0

수정의 수정을 거듭한끝에 100퍼에서 틀렸습니다가 찍힙니다... 무엇을 놓친걸까요 ㅠㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

틀렸습니다가 나옵니다

djdhad 3년 전 0

WeissBlume 3년 전 0

djdhad 3년 전 1

djdhad 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말