fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #define dibs reserve
  13. #define OVER9000 1234567890
  14. #define tisic 47
  15. #define soclose 10e-7
  16. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  17. #define chocolate win
  18. #define ff first
  19. #define ss second
  20. #define uint unsigned int
  21. // mylittlepony
  22. using namespace std;
  23.  
  24. int main() {
  25.     int T;
  26.     cin >> T;
  27.     for(int i =0; i < T; i++) {
  28.     	int N,P;
  29.     	cin >> N >> P;
  30.     	vector<int> p;
  31.     	for(int j =2; j*j <= P; j++) if(P%j == 0) {
  32.     		while(P%j == 0) P /=j;
  33.     		p.push_back(j);}
  34.     	if(P > 1) p.push_back(P);
  35.     	int A =1;
  36.     	for(int i =0; i < p.size(); i++) A *=2;
  37.  
  38.     	vector<int> seq(N+1,0);
  39.     	for(int i =0; i < N; i++) cin >> seq[i+1];
  40.     	vector< vector<int> > B(N+1, vector<int>(A,N+1));
  41.     	B[0][0] =0;
  42.     	// min. number of cuts for this subset of primes
  43.     	for(int i =0; i < N; i++) for(int j =0; j < A; j++) if(B[i][j] <= N) {
  44.     		int s =0;
  45.     		for(int k =i+1; k <= N; k++) {
  46.     			s +=seq[k];
  47.     			int x =j;
  48.     			for(int l =0; l < p.size(); l++) 
  49.     				if(s%p[l] == 0) x |=(1<<l);
  50.     			B[k][x] =min(B[k][x],B[i][j]+1);}
  51.     		}
  52.     	int ans =0, ansC =N;
  53.     	for(int i =0; i < A; i++) if(B[N][i] <= N) {
  54.     		int x =1;
  55.     		for(int j =0; j < p.size(); j++) if((i&(1<<j)) != 0) x *=p[j];
  56.     		if(ans < x) {ans =x; ansC =N;}
  57.     		if(ansC > B[N][i]) ansC =B[N][i];}
  58.     	cout << ans << " " << ansC-1 << "\n";}
  59.     return 0;}
  60.  
  61. // look at my code
  62. // my code is amazing
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
3
2 2
1 2
3 10
9 5 3
4 6
7 1 4 5
stdout
copy 
2 1
5 2
6 1
https://ideone.com/xNxNJD
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!