第八届省赛 B:Quadrat （打表找规律）

阅读量：6095 次

发布时间：2019-06-20

本文共 2544 字，大约阅读时间需要 8 分钟。

Description

It is well-known that for any n there are exactly four n-digit numbers (including ones with leading zeros) that are self-squares: the last ndigits of the square of such number are equal to the number itself. These four numbers are always suffixes of these four infinite sequences:

...0000000000

...0000000001

...8212890625

...1787109376

For example, 09376² =87909376, which ends with 09376.

You are required to count the numbers that are almost self-squares: such that each of the last n digits of their square is at most d away from the corresponding digit of the number itself. Note that we consider digits 0 and 9 to be adjacent, so for example digits that are at most 3 away from digit 8 are 5, 6, 7, 8, 9, 0 and 1.

Input

The first line contains the number of test cases t,1≤t≤72. Each of the next t lines contains one test case: two numbers n(1≤n≤ 18) and d(0≤ d≤3).

Output

For each test case, output the number of almost self-squares with length n and the (circular) distance in each digit from the square at most d in a line by itself.

Sample Input

25 02 1

Sample Output

Hint

In the second case, number 12's almost self-squares are: 00, 01, 10, 11, 15, 25, 35, 66, 76, 86, 90, 91

题意：

求满足以下条件

①.这个数为n位(可以有前导零)

②.取它的平方的后n位，与它本身每一位对应之差≤d(这里的差指的是数字之间的距离，而这个距离是将数字按圈排列，0与9相邻所求得的)

的数字的个数。

题解：

打表吧

规律就是 res[i][j] = res[i-1][j]*(2*j+1)

代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     using namespace std;#define is_lower(c) (c >= 'a' && c <= 'z')#define is_upper(c) (c >= 'A' && c <= 'Z')#define is_alpha(c) (is_lower(c) || is_upper(c))#define is_digit(c) (c >= '0' && c <= '9')#define min(a, b) ((a) < (b) ? (a) : (b))#define max(a, b) ((a) > (b) ? (a) : (b))#define IO \ ios::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0);#define For(i, a, b) for (int i = a; i <= b; i++)typedef long long ll;typedef unsigned long long ull;const ll inf = 0x3f3f3f3f;const double EPS = 1e-10;const ll inf_ll = (ll)1e18;const ll mod = 1000000007LL;const int maxn = 1000000;ll res[20][5];void init() { res[1][0] = res[1][1] = 4; res[1][2] = res[1][3] = 8; for(int i = 2; i < 20; i++) { for(int j = 0;j <= 3; j++) res[i][j] = res[i-1][j] * (2 * j + 1); }}int main() { init(); int T; cin >> T; while(T--){ int n,d; cin>>n>>d; cout << res[n][d] << endl; } return 0;}

转载于:https://www.cnblogs.com/GHzz/p/8666483.html

你可能感兴趣的文章