ACM rightmost digit 求简单思路

发布网友 发布时间：2022-04-22 13:06

我来回答

共3个回答

热心网友 时间：2023-10-14 23:17

看最后一位数字的次方
1的所有次方都是1
0的所有次方都是0
5的所有次方都是5
6的所有次方都是6
2^1=2 2^2=4 2^3=8 2^4=6(四个一循环)
3^1=3 3^2=9 3^3=7 3^4=1(四个一循环)
7^1=7 7^2=9 7^3=3 7^4=1(四个一循环)
4^1=4 4^2=6(两个一循环)
8^1=8 8^2=4(两个一循环)
9^1=9 9^2=1(两个一循环)
故程序如下：
#include<stdio.h>
main()
{
int n,cas,m;
scanf("%d",&cas);
while(cas--)
{
scanf("%d",&n);
m=n%10;
if(m==0||m==1||m==5||m==6) printf("%d\n",m);

if(m==2)
{
if (n%4==1) printf("2\n");
if (n%4==2) printf("4\n");
if (n%4==3) printf("8\n");
if (n%4==0) printf("6\n");
}

if(m==3)
{
if (n%4==1) printf("3\n");
if (n%4==2) printf("9\n");
if (n%4==3) printf("7\n");
if (n%4==0) printf("1\n");
}

if(m==7)
{
if (n%4==1) printf("7\n");
if (n%4==2) printf("9\n");
if (n%4==3) printf("3\n");
if (n%4==0) printf("1\n");
}

if(m==8)
{
if (n%4==1) printf("8\n");
if (n%4==2) printf("4\n");
if (n%4==3) printf("2\n");
if (n%4==0) printf("6\n");
}

if (m==4)
{
if (n%2==1) printf("4\n");
if (n%2==0) printf("6\n");
}

if (m==9)
{
if (n%2==1) printf("9\n");
if (n%2==0) printf("1\n");
}
}
}
很雷人吧，不过也很简单！

热心网友 时间：2023-10-14 23:18

是指求n^n最后那位的那题？
杭电OJ1061
这个可以化简的啊~~~
(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;
}

热心网友 时间：2023-10-14 23:18

# include<stdio.h>
# include<math.h>
int main(){
int n;
while(scanf("%d",&n)!=EOF)
while(n--){
int f,m;
scanf("%d",&m);
f=pow(m,m);
printf("%d\n",f%10);
}
return 0;
}