回家来的第一道题
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip> 10 #include<climits> 11 #include<string.h> 12 #include<cmath> 13 #include<stdlib.h> 14 #include<vector> 15 #define INF 1e7 16 #define MAXN 111111 17 using namespace std; 18 19 20 typedef long long LL; 21 struct node { 22 LL m; 23 int x; 24 bool operator < (const node& a) const { 25 return a.m < m; 26 } 27 }; 28 int n; 29 30 LL bfs() 31 { 32 priority_queue<node> q; 33 node h, t; 34 h.m = 0; 35 h.x = 0; 36 q.push(h); 37 while (!q.empty()) { 38 t = q.top(); 39 q.pop(); 40 LL temp = (LL)pow(10, t.x); 41 if (t.m * t.m % temp == n) 42 return t.m; 43 for (int i = 0; i <= 9; ++i) { 44 h.m = t.m + i*temp; 45 h.x = t.x + 1; 46 if (h.m * h.m % (temp * 10) == n % (temp * 10)) 47 q.push(h); 48 } 49 } 50 return -1; 51 } 52 53 int main() 54 { 55 int t; 56 cin >> t; 57 while (t--) { 58 cin >> n; 59 LL re = bfs(); 60 if (re == -1) puts("None"); 61 else cout << re << endl; 62 } 63 return 0; 64 }