Codeforces - 1107B. Digital root

Question

题目

一个数 x 的数根的定义 S(x) 是如题目中给出的样子（就是一个数不断的将各个位上的数相加得到一个新的数(直到这个数为个位数))，现在给你两个数 k、x ，要你求出第 k 个数根是 x 的非负整数。

解析

想半天没有思路，其实是一道找规律的水题。。

先将前面的结果打表，求出每个数对应的数根，即可以发现规律:

• 是一个以 9 为周期的循环，每个周期的结果都是 1 ~ 9 ；
• 于是很容易得到结果 (k- 1) * 9 + x ；

结果代码以及打表代码:

import java.io.*;
import java.util.*;

public class Main {

    static long getSum(long p){ 
        if(p == 0)
            return 0;
        return getSum(p/10) + p%10;
    }

    static long getRoot(long p){ 
        if(p < 10)
            return p;
        return getRoot( getSum(p) );
    }

    static void test(){ 
        // Bymeter 
        for(int i = 0; i < 100; i++)
            System.out.println( i + " " + getRoot(i) );
    }

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        //test();
        int n = cin.nextInt();
        for(int i = 0; i < n; i++){ 
            long k = cin.nextLong();
            int x = cin.nextInt();
            out.println( (k-1) * 9 + x);
        }
    }
}

题目链接

https://codeforces.com/problemset/problem/1107/B