글 읽기 - 반례좀 찾아주세요..ㅠㅠㅠ;;

kimbabgo 4년 전 1

백만 이하의 소수를 구하고,
N값의 소인수 분해 배열을 구하고.
그것으로 나눈 몫을 빼고(개별 소인수 값, 개별 소인수의 홀수 곱) +더하고(개별 소인수값의 짝수갯수 곱)
해서 값을 구했습니다.;
머가 틀린지 모르겠어요. 아는 범위에서 값을 넣어보면 다 맞는것 같은데...ㅠㅠ;

public class Main{
 static long arr2[];
 static long n;
 public static void main(String[] args) throws Exception{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer sk = new StringTokenizer(br.readLine());
  
  n = Long.parseLong(sk.nextToken());
  
  int a = (int) Math.sqrt(1000000000000l);
  int arr[] = new int[a+1];
  int b = a;//(int) Math.sqrt(a);
  int prm_cnt=0;
  arr[1]=-1;
  long max=0;
  for(int i=2;i<=b;i++) {
   for(long j=(long) i*i;j<=(long) a;j+=i) {
    arr[(int)j]=-1;
   } 
  }
  
  for(int i=1;i<=a;i++) {
   if(arr[i]==0) {
    arr[prm_cnt]=i;
    prm_cnt++;
   }
  }
  
  arr2 = new long[a];
  int cnt2=0;
  for(int i=0;i<prm_cnt;i++) {
   if(n%arr[i]==0) {
    arr2[cnt2]=arr[i];
    cnt2++;
   }
  }
  
  System.out.println(n+rtn(1,0,cnt2,1)); 
 }
 
 static long rtn(int a, int b, int c, long v) {
  long sum=0;
  if(b==c) return sum;
  if(a>c) return sum;
  for(int i=b;i<c;i++) {
   sum=sum+ (long) Math.pow(-1, a)* (long)(n/(v*arr2[i]));
   sum=sum+rtn(a+1,i+1,c,(v*arr2[i]));
  }
  
  return sum;
 }
}

solarmagic 4년 전 0

제가 Java를 별로 안써봐서 정확히 모르는데 위에 import문도 있어야 하지 않나요?
코드를 넣으실 때 import문도 넣어주시길 바랍니다.

1000000007 (소수)
정답: 1000000006
오답: 1000000007

999999999993
정답: 623969559504
오답: 623969562456

kimbabgo 4년 전 1

덕분에 해결했습니다.

말씀하신대로 전소스 올리겠습니다.

감사합니다.

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

문제

문제

출처

ICPC

반례좀 찾아주세요..ㅠㅠㅠ;;

kimbabgo 4년 전 1

solarmagic 4년 전 0

kimbabgo 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말