题解 UVA13216 【Problem with a ridiculously long name but with a ridiculously short description】

· · 题解

AC，我欲也；神犇，我也欲也，二者只能得其一，舍神犇取AC者也。初中生又来发题解了！

题号：UVA13216

难度：★★★

算法：数论、找规律

这题先为大家做一个翻译：

我们有一个任务：输出66的n次方 mod 100。

乍一看貌似还挺容易的，这打暴力求阶乘，最后再 %100不就行了吗？

代码先不展示（我不会告诉你他会WA）

但是我们看看数据，笑容逐渐凝固了……

n是10的1000次方！还能不能好好的游戏了！

n我们能用字符串来表示（字符串是个很无敌的东西），但怎么求答案呢？

答案是不能用字符串表示的了吧，想一想，字符串和数字相转化2n次（字符串->数字->字符串，一共是2次），显然评测机会爆吧。

既然如此，只能用世纪大法——找规律了!

找规律，一种根据前期数字的循环来推出后期的数字的强大知识力量！在大的数字规模之下，一般都会用到它

看到这么大的数字，我们就要来找找规律了：

0 1 2 3 4 5 6 7 8 9 10 11 ……
1 66 56 96 36 76 16 56 96 36 76 16 ……

貌似有些规律对吧……

除了0和1以外，之后一直在以56,96,36,76,16循环！

找到了规律，就能AC了！

上代码：

#include<iostream>
#include<algorithm>
using namespace std;
int n;
string st;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>st;
        if(st=="1")//特判数字1
        {
            cout<<"66"<<endl;
            continue;
        }
        if(st=="0")//特判数字0
        {
            cout<<"1"<<endl;
            continue;
        }
        if(st[st.size()-1]=='2'||st[st.size()-1]=='7')cout<<56<<endl;//按规律输出
        if(st[st.size()-1]=='3'||st[st.size()-1]=='8')cout<<96<<endl;
        if(st[st.size()-1]=='4'||st[st.size()-1]=='9')cout<<36<<endl;
        if(st[st.size()-1]=='5'||st[st.size()-1]=='0')cout<<76<<endl;
        if(st[st.size()-1]=='6'||st[st.size()-1]=='1')cout<<16<<endl;
    }
    return 0;
}

祝大家能AC！