数学 - SGU 118. Digital Root

简介: Digital Root  Problem's Link   Mean:  定义f(n)为n各位数字之和,如果n是各位数,则n个数根是f(n),否则为f(n)的数根.

Digital Root 

Problem's Link


 

Mean: 

定义f(n)为n各位数字之和,如果n是各位数,则n个数根是f(n),否则为f(n)的数根.

现在给出n个Ai,求出A1*A2*…*AN + A1*A2*…*AN-1 + … + A1*A2 + A1 这个式子的数根.

analyse:

这道题目要用到这个规律,设f(n)是n的digital root,那么f(A*N)=f(A*f(N));

 

具体证明过程如下:

  设自然数N=a[n]a[n-1]…a[0],其中a[0],a[1]、…、a[n]分别是个位、十位、…上的数字

  再设M=a[0]+a[1]+…+a[n]

  求证:N≡M(mod 9).

 证明:
   ∵ N=a[n]a[n-1]…a[0]=a[n]*10^n+a[n-1]*10^(n-1)+…+a[1]*10+a[0].
   又∵ 1≡1(mod 9),
   10≡1(mod 9),
   10^2≡1(mod 9),
   …
   10^n≡1(mod 9).
   上面这些同余式两边分别同乘以a[0]、a[1]、a[2]、…、a[n],再相加得:
     a[0]+a[1]*10+…+a[n]*10^n≡(a[0]+a[1]+…+a[n])(mod 9),
                 即 N≡M(mod 9),得证。

  有了这个性质就容易解决本题了

  在计算过程中,可以不断mod 9,因为我们知道有这样两个性质:

 

    (A+B)mod C = ((A mod C) + (B mod C))mod C
    (AB)mod C = ((A mod C)×(B mod C)) mod C

 还要注意,如果余数为0,则输出9.

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-01-08-10.51
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);


#define REP( i, n ) \
   for ( int i = 0; i < (n); i++ )
#define REPD( i, n ) \
   for ( int i = (n) - 1; i >= 0; i-- )
#define FOR( i, b, e ) \
   for ( int i = (b); i <= (e); i++ )

typedef long long int64;

const int MAXN = 1000;

int T , N;
int64 val [ MAXN ];

int droot( int x )
{
    if ( x < 10 ) return x;
    int ans = 0;
    while ( x > 0 )
    {
        ans += x % 10;
        x /= 10;
    }
    return droot( ans );
}

int main()
{
    scanf( "%d" , & T );
    while ( T -- )
    {
        scanf( "%d" , &N );
#warning READ LLD
        REP( i , N )
        scanf( "%I64d" , & val [ i ] );
        int64 ans = droot( val [N - 1 ] );
        REPD( i , N - 1 )
        ans = droot( droot( val [ i ]) * droot( ans + 1) );
        printf( "%I64d \n " , ans );
    }

    return 0;
}

 

目录
相关文章
|
7月前
|
存储
六道入门树题目带你走入树结构的世界-liu-dao-ru-men-shu-ti-mu-dai-ni-zou-ru-shu-jie-gou-de-shi-jie
六道入门树题目带你走入树结构的世界-liu-dao-ru-men-shu-ti-mu-dai-ni-zou-ru-shu-jie-gou-de-shi-jie
30 0
luogu CF776D The Door Problem(2-sat问题)
luogu CF776D The Door Problem(2-sat问题)
65 0
|
算法
聪明的KK【ACM】
聪明的KK【ACM】
97 0
2019CCPC秦皇岛HDU - 6736 F - Forest Program(dfs找环 组合数学)
2019CCPC秦皇岛HDU - 6736 F - Forest Program(dfs找环 组合数学)
101 0
|
移动开发
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
HDOJ 2200 Eddy's AC难题(数学组合概率题)
HDOJ 2200 Eddy's AC难题(数学组合概率题)
112 0
HDOJ(HDU) 2309 ICPC Score Totalizer Software(求平均值)
HDOJ(HDU) 2309 ICPC Score Totalizer Software(求平均值)
102 0