Submission #7443327


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define debug(x) cerr<<#x<<":"<< (x)<<endl;

//
// eratosthenes
//  + 値は1-indexedで格納されている
//  + prime
//    - 素数か否かがbool型で格納
//    - prime[n] ? 素数 : 素数ではない
//  + prime_factorize
//    - 素因数分解をする関数
//    - 引数nを素因数分解して, 
//      どの素数がどれだけ含まれているかをvector< pair<int,int> >で返す 
//    - e.g.) n=20 => (2,2), (5,1)

struct Eratosthenes {
	// 1-indexedで検索可能
  vector< bool > prime;
  // sizeは1e6くらいまでならおk
  Eratosthenes(int _size) {
    init(_size);
  }	
	
  void init(int n) {
    prime.resize(n + 1);
    for(int i=0; i<prime.size(); ++i) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i=2; i*i<=n; i++) {
      if (prime[i]) {
        for (int j=0; i*(j + 2)<n; ++j) {
					prime[i*(j+2)] = false;
				}
      }
    }
  }

	vector< pair< int, int > > prime_factorize(int n) {
		vector< pair< int, int > > res;
		for (int p=2; p*p<=n; ++p) {
			if (n%p != 0) continue;
			int num = 0;
			while (n%p == 0) ++num, n /= p;
			res.push_back(make_pair(p, num));
		}
		if (n != 1) res.push_back(make_pair(n, 1));
		return res;
	}
};

signed main() {
  int n,p;cin>>n>>p;
  Eratosthenes e(1);
  vector< pair<int,int> > ps = e.prime_factorize(p);
  int ans = 1;
  for(int i=0;i<ps.size();++i){
    if (ps[i].second/n==0) continue;
    for (int j=0;j<ps[i].second/n;++j){
      ans *= ps[i].first;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task C - Product and GCD
User task4233
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1659 Byte
Status
Exec Time 6 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
× 4
× 34
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt, sample4.txt
All sample1.txt, sample2.txt, sample3.txt, sample4.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt
Case Name Status Exec Time Memory
1.txt 2 ms 256 KB
10.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 1 ms 256 KB
16.txt 1 ms 256 KB
17.txt 3 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
2.txt 2 ms 256 KB
20.txt 1 ms 256 KB
21.txt 1 ms 256 KB
22.txt 2 ms 256 KB
23.txt 6 ms 256 KB
24.txt 1 ms 256 KB
25.txt 1 ms 256 KB
26.txt 1 ms 256 KB
3.txt 1 ms 256 KB
4.txt 1 ms 256 KB
5.txt 1 ms 256 KB
6.txt 1 ms 256 KB
7.txt 2 ms 256 KB
8.txt 2 ms 256 KB
9.txt 1 ms 256 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB
sample4.txt 1 ms 256 KB