SRM529 Div2 Hard

1000
ここを見る

view plainprint?

1. class MinskyMysteryDiv2 {  
2. public:  
3.   long long computeAnswer(long long N)   
4.   {  
5.     if (N == 0) return -1;  
6.   
7.     const int P = 1000000;      
8.     bool prime[P];  
9.   
10.     fill(prime, prime + P, true);  
11.     prime[0] = prime[1] = false;  
12.   
13.     for (lli i = 2; i * i < P; ++i) {  
14.       for (lli j = 2; i * j < P; ++j) {  
15.         prime[i * j] = false;  
16.       }  
17.     }         
18.   
19.     lli mn = 9999999999991LL;  
20.     lli M = N;  
21.     for (lli i = 1; i < P; ++i) {  
22.       if (prime[i]) {  
23.         while (M % i == 0) {  
24.           mn = min(mn, i);  
25.           M /= i;  
26.         }  
27.       }  
28.     }  
29.     if (M != 1LL) mn = min(mn, M);  
30.   
31.     lli mx = 1;  
32.     for (lli i = 2; i * i <= N; ++i) {  
33.       if (N % i == 0) {  
34.         mx = max(mx, i);  
35.         mx = max(mx, N / i);  
36.       }  
37.     }  
38.   
39.     lli res = mn + mx;  
40.     return res < 9999999999991LL ? res : -1;  
41.   }  
42.   
43. };  

class MinskyMysteryDiv2 {
public:
  long long computeAnswer(long long N) 
  {
    if (N == 0) return -1;

    const int P = 1000000;    
    bool prime[P];

    fill(prime, prime + P, true);
    prime[0] = prime[1] = false;

    for (lli i = 2; i * i < P; ++i) {
      for (lli j = 2; i * j < P; ++j) {
        prime[i * j] = false;
      }
    }       

    lli mn = 9999999999991LL;
    lli M = N;
    for (lli i = 1; i < P; ++i) {
      if (prime[i]) {
        while (M % i == 0) {
          mn = min(mn, i);
          M /= i;
        }
      }
    }
    if (M != 1LL) mn = min(mn, M);

    lli mx = 1;
    for (lli i = 2; i * i <= N; ++i) {
      if (N % i == 0) {
        mx = max(mx, i);
        mx = max(mx, N / i);
      }
    }

    lli res = mn + mx;
    return res < 9999999999991LL ? res : -1;
  }

};