`
mars914
  • 浏览: 432844 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Rightmost Digit

阅读更多

Problem Description

Given a positive integer N, you should output the most right digit of N^N. 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output

For each test case, you should output the rightmost digit of N^N.

Sample Input

2

3

4 

Sample Output

7

6

Hint

 

In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.

In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.

可以发现一个规律:
当   n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 ...
rdigit = 1 4 7 6 5 6 3 6 9   0   1   6  3   6   5   6   7   4  9  0  1   4   7   6   5   6   3   6  9   0    ...
所以是以20为周期的规律。
得到这个规律,算法就变得很easy
#include<iostream>
using namespace std;
int main()
{
    int  rdigit[20] = {0,1,4,7,6,5,6,3,6,9,0,1,6,3,6,5,6,7,4,9};
    int n;
    cin>>n;
    int res[n];
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        res[i]=rdigit[temp%20];
    }    
    for(int i=0;i<n;i++)
    {
        cout<<res[i]<<endl;
    }
    system("pause");
    return 0;
}    
 
分享到:
评论
1 楼 mars914 2012-04-13  
是指求n^n最后那位的那题?
这个可以化简的啊~~~
(a*b)%n=((a%n)*(b%n))%n
所以呢~
完全可以乘一次n,再求一次10的余数。然后对余数进行下一次的次方操作~
若n太大,则可用二进制优化,将n看作是二进制,例如8=1000
然后,n^8=(n^4)^2,这样算一次n^4就等于算了两次n^4了~
附上代码~
#include<stdio.h>
#include<stdlib.h>

int rightD(int n)
{
int ans=1;
int a=n,b=n;
a%=10;
while(b)
{
if(b%2==1)
{
ans*=a;
ans%=10;
}
b/=2;
a*=a;
a%=10;
}
return ans;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",rightD(n));
}
return 0;
}

相关推荐

    Rightmost Digit_hdu_

    【标题】"Rightmost Digit HDU" 这道题目来源于HDU(杭州电子科技大学)的在线判题系统,通常这类题目是编程竞赛或者算法训练的一部分。"Rightmost Digit"直译为“最右边的数字”,我们可以推测这是一个关于数字...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    (lecture_02)简单数学题

    **快速幂取模(Rightmost Digit)**:给定一个正整数N,求N的N次方的最右边的数字。对于大数据规模,直接暴力计算会导致超时。可以采用模幂运算和位运算优化,例如每次计算2的幂,然后根据规律求解。\n\n3. **位...

    ACM杭电入门训练题

    - **Rightmost Digit**: 数学运算题目,要求找出一个数的最右位数字。 - **Fibonacci Again**: 斐波那契数列题目,要求高效计算斐波那契数列的某个值。 - **Coin Change**: 经典的组合数学题目,要求找出最少硬币...

    python-leetcode面试题解之第55题跳跃游戏-题解.zip

    rightmost = max(rightmost, i + nums[i]) return dp[-1] ``` 在这段代码中,我们首先初始化一个全为False的状态数组dp,然后从第一个位置开始,依次检查每个位置是否可以从已达到的位置跳跃过来。如果有,我们就...

    nim_组合数学

    There are an odd number of 1’s among the rightmost digits, so this position is not losing. However, suppose k3 were changed to be 12. Then, there would be exactly two 1’s in each digit position, and...

    AIX5.3及6.1堆溢出漏洞利用原理分析

    劳伟的文章通过对AIX5.3/6.1堆溢出漏洞利用机制的深入分析,不仅为我们揭示了rightmost和leftmost函数在堆管理中的作用,还提出了一种新的利用机制并通过CDE ToolTalk数据文件解析漏洞的有效性验证。此外,文章还从...

    二叉树展开为链表(java代码).docx

    rightmost = rightmost.right; } // 将原先的右子树接到左子树的最右结点后面 rightmost.right = node.right; node.right = node.left; node.left = null; } node = node.right; } } } ``` **时间复杂度*...

    MATLAB求一个圆的直径半径

    radius = (rightmost - leftmost) / 2; ``` 圆心的x坐标是这两个点的平均值,y坐标需要额外的步骤来确定,因为一个简单的平均可能会落在非边缘像素上。一种方法是找到这两点连线上的所有边缘像素,然后找到它们的...

    LR-fenxi.rar_LR_LR 分析器_LR分析器_lr 分析

    LR(Lookahead Rightmost Derivation)分析方法基于自底向上的方式处理语法,它结合了预测(Lookahead)和右最简推导(Rightmost Derivation)的概念。在本压缩包“LR-fenxi.rar”中,包含了一个名为“LR-fenxi.doc...

    左倾树数据结构

    1. 令 x 是权值左倾树中任意的内部结点,从 x 沿最右支路径到外部结点的路径长度 rightmost(x) 满足下式:rightmost(x) (w(x)+1)。 权值左倾树的融合操作相比高度左倾树的融合操作要快一个常数倍因子。这是因为,在...

    编译原理实验报告,词法分析,语法分析,语义分析。

    LR(Left-to-right,Rightmost Derivation)、LL(Left-to-right,Leftmost Derivation)或LALR(Lookahead Left-to-right,Rightmost Derivation)等解析策略常用于构建语法分析器。 3. **语义分析**(Semantic ...

    编译原理 语法分析

    在本资料合集中,重点讨论的是LR(Look-Ahead Rightmost Derivation)语法分析方法。 LR分析是一种自底向上的语法分析技术,它通过一个称为LR解析表的工具来指导解析过程。"LR"这个缩写代表“Look-Ahead Rightmost ...

    一个SLR,LR,LALR语法分析器源代码

    SLR(Simple Left-to-Right, Rightmost Derivation)分析器: SLR分析器是一种最简单的LR分析器,它按照自左向右扫描输入串,并采用最右推导的方式进行解析。SLR分析器的工作原理是通过构建一个状态转移表,每个状态...

    Python库 | GLRParser-0.3.4.tar.gz

    **GLRParser-0.3.4.tar.gz** 是一个针对Python编程语言的解析库,主要功能是实现Generalized Leftmost-Rightmost (GLR) 解析算法。GLR解析是一种扩展自LR(Left-to-Right, Rightmost-derivation)解析的方法,它能...

    编译原理 LR(0),SLR(1),LR(1), LALR(1) 词法分析

    LR(0) 分析是一种自底向上的语法分析方法,其中“L”代表Left-to-right扫描输入,“R”代表Rightmost derivation,而“0”表示没有查看任何未来的输入符号。LR(0) 分析器基于状态机,每个状态包含一个项目集,项目集...

    基于Java的实例源码-编译原理-LR(1)分析表构造(JAVA).zip

    LR分析是Lookahead Rightmost Derivation的缩写,它是一种自底向上、从右到左的语法分析方法。其中,L代表Left-to-right扫描输入,R代表Rightmost derivation,即最右推导。而1则代表每一步分析时使用的1个输入符号...

    编译原理 - LR(1)分析法:C/C++实现

    LR(1)(Left-to-Right, Rightmost derivation with 1 symbol lookahead)分析法是一种用于构建分析器的语法分析方法,通常用于分析上下文无关文法的语法结构,属于LR分析法的一种变种。它是一种强大的自底向上语法...

    编译原理SLR1分析

    LR 分析(Lookahead Rightmost Derivation)是一种自底向上的语法分析方法,LR 表示“Left-to-Right扫描输入,Rightmost Derivation”。SLR1 是 LR 分析的一个变种,"1" 表示它使用一个符号的向前看(lookahead)...

Global site tag (gtag.js) - Google Analytics