Skip to content

Instantly share code, notes, and snippets.

@bhi5hmaraj bhi5hmaraj/LA_5116.java
Last active Nov 11, 2017

Embed
What would you like to do?
AC code
import java.util.*;
import java.io.*;
public class LA_5116 {
/************************ SOLUTION STARTS HERE ************************/
static int P;
static int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
static HashSet<Integer> set;
static void rec(int idx , int n , int val) {
set.add(val);
if(val > 0 && idx < primes.length && n >= 0) {
int curr = 1;
for(int i = 0; n - primes[idx] * i >= 0; i++) {
rec(idx + 1, n - primes[idx] * i, (int) ((1L * val * curr) % P));
curr = (int) ((1L * curr * primes[idx]) % P);
}
}
}
private static void solve() {
int T = nextInt();
while(T-->0) {
int N = nextInt();
P = nextInt();
set = new HashSet<>();
rec(0, N, 1);
println(set.size());
}
}
/************************ SOLUTION ENDS HERE ************************/
/************************ TEMPLATE STARTS HERE **********************/
public static void main(String[] args) throws IOException {
reader = new BufferedReader(new InputStreamReader(System.in));
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
st = null;
solve();
reader.close();
writer.close();
}
static BufferedReader reader;
static PrintWriter writer;
static StringTokenizer st;
static String next()
{while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}
st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
static String nextLine() {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}
static int nextInt() {return Integer.parseInt(next());}
static long nextLong() {return Long.parseLong(next());}
static double nextDouble(){return Double.parseDouble(next());}
static char nextChar() {return next().charAt(0);}
static int[] nextIntArray(int n) {int[] a= new int[n]; int i=0;while(i<n){a[i++]=nextInt();} return a;}
static long[] nextLongArray(int n) {long[]a= new long[n]; int i=0;while(i<n){a[i++]=nextLong();} return a;}
static int[] nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;}
static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;}
static void print(Object o) { writer.print(o); }
static void println(Object o){ writer.println(o);}
/************************ TEMPLATE ENDS HERE ************************/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.