This was a quite hard problem. In order to solve it, fb(n) must be at most log(n). We need to split base number into prime factors and precompute modulo values for every prime up to (prime^k)^5. Then for every prime factor we must calcultate fb_prime(n) mod (prime^k)^5. At the begining we must strip trailing zeroes by multiplying by proper inverses of other primes. This is a little bit tricky and requires carefull analysis. Computing the product factors thar are comprime to given prime can be computed in log(n) time using previously precomputed values mod prime^5k. Finally we must solve a system of linear congruences using Chinese Reminder Theorem.

Hi, can someone help me with the code? I am able to pass all test cases that I enter manually. Tried with 22b16, 22b10, 20b10, 20b16, 10b10, 10b9, 22b2 etc. However, the code is only passing testcase 0;

public static void main(String[] args) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
    Scanner scan = new Scanner(System.in);
    int b = scan.nextInt();
    int q = scan.nextInt();
    for(int i = 0; i < q; i++)
    {
        int n = scan.nextInt();
        long ans = factorial(n, b);
        System.out.println(toBase(ans, b));
    }
}
public static long factorial(int n, int b)
{
    long ans = 1; int digits5 = b*b*b*b*b;
    for(int i = 2; i <= n; i++)
    {
        ans = ans * i;
        // remove trailing zeros
        while(true){ if(ans % b == 0) ans = ans/b; else break;}
        // keep only last 5 digits
        ans = ans % digits5;
    }
    return ans;
}
static char[] bases = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 
                'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
public static String toBase(long ans, int base)
{
    char[] digits = new char[20]; int count = 0;
    for(int i = 0; i < 20; i++)
    {
        int k = (int) (ans % base);
        digits[i] = bases[k]; ans = ans / base; count++;
        if(ans < base) {digits[i+1] = bases[(int) ans]; count++; break;}
    }
    char[] digitNew = new char[count];
    // need to reverse digits
    for(int j = 0; j < count; j++)
        digitNew[count-1-j] = digits[j];
    return new String(digitNew);
}

Hi, can someone help me with my code. I could pass only 1 test case. For other test cases it say terminated due to timeout.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int base,n;
   // cout <<" enter base" <<endl;
    cin >> base;
   // cout <<"Enter the value of n"<<endl;
    cin >> n;
    int arr[n];
  //  cout <<"Enter the array"<<endl;
    for(unsigned int i=0;i<n;i++)
    {
     cin >> arr[i];   
        
    }
    
    for(int i=0;i<n;i++)
        {
  long long unsigned  int fact = 1;
        for(unsigned int j=1;j<=arr[i];j++)
            {
            fact=fact*j;
        }
      //  cout << fact << " ";
        while((fact % base) == 0)
            {
            fact=fact/10;
        }
        cout << (fact%100000) <<endl;
    }
    return 0;
}

Hi, I am trying to solve the problem using Python. I am getting pass the first test case, but my code is failing rest all of the test cases. Admin can you please provide us with some complex test cases with different base value to show what is the input and what is expected output.

i cant get the base one