琪露诺的算术教室
Time Limit: 1000ms
Memory Limit: 65536KB
Description
给出一个非负整数A,将这个数字的最低位移动到最高位(原来的最高位变为次高位,次低位变成最低位),得到非负整数B,发现B恰好是A的k倍。现给出A的最低位的值n,和倍数k,求最小的非负整数B。
Input
第一行输入一个正整数T(1 <= T <= 1000),表示有T组测试数据。对于每组测试数据:输入两个整数n,k(0<=n<=9,0<=k<=9)。
Output
对于每组测试数据,输出一个非负整数B,若无解,请输出-1。
Sample Input
1 2 2Sample Output
210526315789473684
题目链接:https://icpc.njust.edu.cn/Problem/Local/1926/
题目分析:也就wa了14发吧,比赛结束前30毫秒AC,就是解方程,特判情况比较多,而且结果爆long long,方程就是k * (10 * x? + n)? = x + n * (10 ^ c),枚举c,解x,判断x是不是c位数,加几个特判,n和k都是0是答案是0,k=1是答案是n,因为只有一个数字,怎么移都是自己的一倍,n=0时答案显然是0,n小于k或者k等于0显然无解。直接java跑大数
import java.io.*; import java.math.*; import java.util.*; public class Main { public static BigInteger pp(BigInteger x,int n){ BigInteger res = BigInteger.ONE; for(int i = 1; i <= n; i++) res = res.multiply(x); return res; } public static int calw(BigInteger x){ String s = x.toString(); int len = s.length(); return len; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); for(int i = 0; i < T; i++) { int n = in.nextInt(); int k = in.nextInt(); if(n == 0 && k == 0){ System.out.println(0); continue; } if(k == 1) { System.out.println(n); continue; } if(n == 0){ System.out.println(0); continue; } if(n < k){ System.out.println(-1); continue; } if(k == 0){ System.out.println(-1); continue; } boolean flag = false; for (int t = 0; t <= 100 && flag == false; t++) { BigInteger tmp = pp(BigInteger.valueOf(10),t); tmp = tmp.subtract(BigInteger.valueOf(k)); BigInteger a = BigInteger.valueOf(n).multiply(tmp); tmp = BigInteger.valueOf(10).multiply(BigInteger.valueOf(k)); BigInteger b = tmp.subtract(BigInteger.ONE); if (a.compareTo(b) >= 0 && a.mod(b).compareTo(BigInteger.ZERO) == 0) { BigInteger x = a.divide(b); int w = calw(x); if (w == t) { BigInteger ans = x.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(n)); ans = ans.multiply(BigInteger.valueOf(k)); System.out.println(ans); flag = true; } } } if (flag == false) System.out.println(-1); } } }