sgu 118

Posted on 2010-12-15 11:48 王之昊 阅读(187) 评论(0)  编辑 收藏 引用 所属分类: sgu
对于“数根”（定义见Let f(n) be a sum of digits for positive integer n. If f(n) is one-digit number then it is a digital root for n and otherwise digital root of n is equal to digital root of f(n).）注意这里只定义正整数的“数根”，所以已经把 0 排除了。

结论: 数根f(n)与n模9同余，且f(n)的范围属于[1,9].

证明：如果n = am*10m + am-1*10m-1 +...+ a0*100 , 令g(n) = am+am-1+...+a0.    

n       ->        [n0=g(n)]      ->        [n1=g(n0)]       ->         [n2=g(n1)]       ->        ...      ->        f(n) 

中间的每个环节都是模9同余的，传递下去，所以n和f(n)也是模9同余的

 1
 2import java.io.FileNotFoundException;
 3import java.util.Scanner;
 4
 5
 6/*
 7 * To change this template, choose Tools | Templates
 8 * and open the template in the editor.
 9 */
10/**
11 *
12 * @author wangzhihao
13 */
14class Seq {
15
16    int[] A;
17
18    Seq(int[] a) {
19    A = a;
20    }
21    int DigitSum() {
22    int res = 0, term = 1;
23    for (int i = 0; i < A.length; i++) {
24        term = term * ( A[i] % 9) % 9;
25        res = ( res + term ) % 9;
26    }
27    return res == 0 ? 9 : res;
28    }
29}
30
31public class Solution {
32
33    /**
34     * @param args the command line arguments
35     */
36    public static void main(String[] args) throws FileNotFoundException {
37    Scanner sc = new Scanner(System.in);
38    int testCase = sc.nextInt();
39    for (int cas = 1; cas <= testCase; cas++) {
40        int n = sc.nextInt();
41        int[] a = new int[n];
42        for (int i = 0; i < n; i++) {
43        a[i] = sc.nextInt();
44        }
45        Seq seq = new Seq(a);
46        System.out.println(seq.DigitSum());
47    }
48    }
49}
50


只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊