HDU-1163 Eddy's digital Roots

末蓝、 2023-06-30 01:43 29阅读 0赞

**前置芝士**: 同余定理，快速幂

这个题目是杭电上的一道数论相关的题目  
如果暴力的话是一定会超时的，这个时候我们就要用到同余定理来优化。

同余定理是数论中的重要概念，下面贴上百度百科的定义：[同余定理][Link 1]

> **给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。**

在这里我们简单地证明一下：  
对于给定的十进制数 x = 1000 ∗ a + 100 ∗ b + 10 ∗ c + d x=1000\*a+100\*b+10\*c+d x=1000∗a\+100∗b\+10∗c\+d我们将这个式子进行转换  
 x = 9 ( 99 ∗ a + 9 ∗ b + c ) + ( a + b + c + d ) x=9(99\*a+9\*b+c)+(a+b+c+d) x=9(99∗a\+9∗b\+c)\+(a\+b\+c\+d)因为9一定能整除 3 和 9 ，所以只要  ( a + b + c + d ) (a+b+c+d) (a\+b\+c\+d) 能除尽 9 。那么  x x x 也一定能除尽3和9。  
所以我们可以认为 x ≡ ( a + b + c + d ) ( m o d 9 ) x≡(a+b+c+d)( mod 9) x≡(a\+b\+c\+d)(mod9)  
那么根据这个定理我们就可以很容易得出题目的解法

假设  N N = 1234567 N^N=1234567 NN=1234567 , 那么  1234567 m o d 9 = 1 1234567 mod 9=1 1234567mod9=1  1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 1+2+3+4+5+6+7=28 1\+2\+3\+4\+5\+6\+7=28 28 m o d 9 = 1 28mod9=1 28mod9=1 2 + 8 = 10 2+8=10 2\+8=10 10 m o d 9 = 1 10mod9=1 10mod9=1 1 + 0 = 1 1+0=1 1\+0=1 1 m o d 9 = 1 1mod9=1 1mod9=1  
**所以  N N N^N NN 的数字根 =  N N % 9 N^N\\%9 NN%9**

### 注意 **当  N N % 9 = 9 N^N\\%9=9 NN%9=9 时,对应的数字根为  9 9 9!** ###

本题因为 N N N的范围过大,所以要配合快速幂来使用

代码如下:

#include<bits/stdc++.h> 
    using namespace std;
    int qPow(long long A , long long x)  //A^x
    { 
        if (x == 0) return 1;
        long long ans = 1;
    
        while (x)
        { 
            if ( x & 1) 	//如果n的尾数为1; 
            { 
                ans = ans * A % 9 ;  // ans = ans * A % 10
            }
            A = A * A % 9; 	// A = A * A % 10
            x >>= 1;  
        }
        return ans;
    }
    int main()
    { 
    	int n,ans;
    	
    	while(~scanf("%d",&n) && n)
    	{ 
    		ans=qPow(n,n);
    		printf("%d\n",ans==0? 9:ans);
    	}
    	return 0;
    }

参考博客：  
[https://www.cnblogs.com/zzqc/p/6684794.html][https_www.cnblogs.com_zzqc_p_6684794.html]  
[https://blog.csdn.net/Techmonster/article/details/50113789][https_blog.csdn.net_Techmonster_article_details_50113789]

[Link 1]: https://baike.baidu.com/item/%E5%90%8C%E4%BD%99%E5%AE%9A%E7%90%86/1212360?noadapt=1
[https_www.cnblogs.com_zzqc_p_6684794.html]: https://www.cnblogs.com/zzqc/p/6684794.html
[https_blog.csdn.net_Techmonster_article_details_50113789]: https://blog.csdn.net/Techmonster/article/details/50113789