NJUST 1926 琪露诺的算术教室 (解方程 大数)

琪露诺的算术教室

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 2

Sample 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);
        }
    }
}

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注