0008 ALGO999-数的潜能

试题 算法训练 数的潜能

可以转换为将数分解为多少个 3，再处理余数即可。为什么不分解为 2，因为 2³ = 8 < 9 = 3 ²。

加上较小值得处理，输入值 \(\le 4\) 时，直接输出即可。

对于 \(3^N\) 的处理，由于 \(3^7 < 5218 < 3^8\) ，可以转为 \({(3^8 \% 5218)}^{N / 8}\)，依次类推，直至 N 无法继续缩减

较小值的处理参考：蓝桥杯 算法训练 数的潜能（Java）

import java.util.Scanner;

/**
 * @author HuaWang135608
 * @date 2023.03.18 09:48:39
 * @description [试题 算法训练 数的潜能](http://lx.lanqiao.cn/problem.page?gpid=T2984)
 */

public class A0999_PotentialofNumber {

	public static void main(String[] args) {
		long src;
		long res;
		
		// 数据输入
		try (Scanner sc = new Scanner(System.in)) {
			src = sc.nextLong();
		}
		
		// 数据处理
		long index_2 = 0;
		long index_3 = src / 3; // 将数据分解为 3 的和
		switch ((int) (src - index_3 * 3)) {
		case 1: // 余数等于 1 则 3 修正为 4
			--index_3;
			index_2 = 2;
			break;
		case 2: // 余数等于 2 则加一个
			index_2 = 1;
			break;
		}
		
		if (src <= 4) { // 1~4 均为原始值 4 = 2 + 2；1，2，3不清楚为什么
			res = src;
		} else {
			res = 1;
			res  <<= index_2;
			
			long base = 3;
			long index = index_3;
			int sub = getIndex(base); // 获取 base^index >大于 5218 的最小 index
			while (index >= sub) {
				res *= (long) (Math.pow(base, index % sub)); // 获取剩余的指数
				res %= 5218; // 对 5218 取余
				if (res == 0) { // 可以整除 5218 则直接退出
					break;
				}
				
				base = ((long)(Math.pow(base, sub)) % 5218); // 获取余下的底数
				if (base == 1) { // 底数为 1 不影响结果
					break;
				} else if (base == 0) { // 底数为 0 可被整除
					res = 0;
					break;
				}
				index = index / sub; // index 向下缩减
				sub = getIndex(base); // 更新最小的指数
			}
			
			if (index>0 && base>1) {
				res *= (long)(Math.pow(base, index));
			}
			res %= 5218; // 再次取余
		}
		
		// 结果输出
		System.out.println(res);
	}
	
	public static int getIndex(long base) {
		int index = 1;
		long src = base;
		while (src < 5218) {
			src *= base;
			++index;
		}
		return index;
	}
}