As always you could try with brute force method to detect repeating patterns, however, you will find difficulties with so called mixed repeating decimals.
For example 1/6 is 0.166666.... so if you trying to queue numbers, and try to match pattern, you might face some issues given the fact that prefix before repeating pattern is not determined.
So instead, I decided to queue remainders each step after. You will get more idea instead of reading this wordy explanation. See implementation below in both Java and C.
One more thing, to optimize a little bit, I assumed that fact that repeating decimal of non-prime is shorter than repeating decimal of prime number. I will omit proof of this idea.
C:
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int get_answer(int N); int generate_data(int N); int DATA[10001]; int LIST[10001]; int main() { int T, N; generate_data(10000); cin >> T; while (T--) { cin >> N; cout << get_answer(N) << endl; } return 0; } int get_answer(int N) { int MAX = -1; int index = 1; for (int i = 3; i < N; i++) { if (DATA[i] > MAX) { MAX = DATA[i]; index = i; } } return index; } int is_prime(int N) { int i; if(N%2 == 0) return 1; if(N%3 == 0) return 1; for (i=3;i<=sqrt(N);i+=2) { if(N%i == 0) return 0; } return 1; } int generate_data(int N) { double n; int q, index, count, flag; int max = -1, max_index = 0; for (int i = 3; i <= N; i++) { n = 1; flag = 0; count = 0; if (i % 5 == 0 || i % 2 == 0) { DATA[i] = 0; continue; } if (i > 5 && !is_prime(i)) { // cout << i << " is prime." << endl; DATA[i] = 0; continue; } index = 0; while (true) { while (n < i) { n *= 10; } n = fmod(n, (double) i); if (n == 0) { index = 0; break; } int count2; if (count > 10) { count2 = 10; } else { count2 = count; } for (int j = 0; j < count2; j++) { if (LIST[j] == n) { flag = 1; break; } } if (flag) { break; } LIST[count++] = n; } DATA[i] = count - index; if (DATA[i] > max) { max = DATA[i]; max_index = i; } } return max_index; }
Java:
import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Solution { private static HashMap<Integer, Integer> DATA = new HashMap<Integer, Integer>(); public static void main(String[] args) { int T, N; Scanner sc = new Scanner(System.in); generateData(); T = sc.nextInt(); while (T-- > 0) { N = sc.nextInt(); System.out.println(getAnswer(N)); } sc.close(); } private static void generateData() { int n, q, index; ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 3; i <= 10000; i++) { n = 1; if (i % 5 == 0) { DATA.put(i, 0); continue; } index = 0; while (true) { while (n < i) { n *= 10; } n %= i; // System.out.println("i:" + i + " n:" + n); if (n == 0) { index = 0; break; } if (list.contains(n)) { index = list.indexOf(n); break; } list.add(n); } DATA.put(i, list.size() - index); list.clear(); } } private static int getAnswer(int N) { int MAX = Integer.MIN_VALUE; int index = 1; for (int i = 3; i <= N; i++) { if (DATA.get(i) != null && DATA.get(i) > MAX) { MAX = DATA.get(i); index = i; } } return index; } }
