AcWing 666. 求自守数
原题链接
中等
作者:
Misty.
,
2024-10-27 15:42:23
,
所有人可见
,
阅读 10
题目背景:
如果某个数的平方的末尾几位等于该数自身,那么就称这个数为自守数。例如,0和1的平方的个位数仍然是0和1,所以0和1是自守数,称为平凡自守数。很显然,5和6是一位自守数,因为5×5=25,6×6=36。而25和76是两位自守数,因为25×25=625,76×76=5776,当然还有三位自守数,四位自守数等等,在此不再一一介绍。
自守数有一个特性,以它为后几位的两个数相乘,乘积的后几位仍是这个自守数。因为5是自守数,所以以5为个位数的两个数相乘,乘积的个位仍然是5;76是自守数,所以以76为后两位数的两个数相乘,其结果的后两位仍是76,如176×576=101376。
案例要求编程求出0~10000内的所有自守数,并依次输出到屏幕上。
#include <math.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
int mul=n;
int k=0;
while(mul!=0) //获取n的位数,记录在k里~
{
k++;
mul/=10;
}
int res=0;
/*在每一次的部分积中,并不是它的每一位都会对积的后三位产生影响。总结规律可以得到:在三位数乘法中,对积的后三位产生影响的部分积分别为:
✪ 第一个部分积中:被乘数最后三位×乘数的倒数第一位。
✪ 第二个部分积中:被乘数最后二位×乘数的倒数第二位。
✪ 第三个部分积中:被乘数最后一位×乘数的倒数第三位。
如376 我们只需获取,6*376+70*76+3*376=9376 即可判断。 其确实是个自守数
376
*376
*/
int p=10; //p用来获取6,70,300
int w=pow(10,k);//w用来获取376,76,6
cout<<p<<endl<<w<<endl;
for(int i=1;i<=k;i++)
{
int a=n%p-n%(p/10); //这里是6,76-6=70,376-76=300
int b=n%w;//这里是376,76,6
cout<<a<<"*"<<b<<"="<<a*b<<endl;
res+=a*b; //每次把累加和求出来
p=p*10; //处理获取工具
w=w/10;
}
cout<<res; //再比照后k位是否相等即可~
return 0;
}