首页 > 代码库 > URAL 1698. Square Country 5(记忆化搜索)
URAL 1698. Square Country 5(记忆化搜索)
题目链接
题意 : 自守数的定义:如果某个数的平方的末尾几位数等于这个数,那么就称这个数为自守数。例如5*5=25,则5就是自守数。让你求不超过n位的自守数有多少
思路 : 实际上,自守数还有两个性质:以他为后几位的两个数相乘,乘积的后几位仍是这个自守数。刚好n位的自守数一定是两个,当然1位的时候0和1是没有算进去的,但是题目中1是要加上的,所以从第0位深搜枚举到第n位。还有另一种方法,因为一个数是自守数当且仅当这个数是另一个自守数的后缀,2000位的自守数只有两个,所以存下来直接数也行
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 5 using namespace std ; 6 int n,ans ; 7 int a[2100],b[2100] ; 8 9 bool check(int k)10 {11 b[k] = 0 ;12 for(int i = 0 ; i <= k ; i++)13 {14 b[k] += a[i]*a[k-i] ;15 }16 if(k) b[k] += b[k-1]/10 ;17 return b[k] % 10 == a[k] ;18 }19 20 void dfs(int k)21 {22 if(k >= n) return ;23 for(int i = 9 ; i >= 0 ; i--)24 {25 a[k] = i ;26 if(check(k))27 {28 if(a[k]) ans++ ;29 dfs(k+1) ;30 }31 }32 }33 int main()34 {35 while(~scanf("%d",&n))36 {37 ans = 0 ;38 dfs(0) ;39 printf("%d\n",ans) ;40 }41 return 0 ;42 }
URAL 1698. Square Country 5(记忆化搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。