这道题目的意思是给你提供a, b, n 三个数
a为 输入的数字 ，你需要在ａ后面加ｎ次 ，每次可以加0-9
但要保证每次加上去的那个数字能被b整除
不过数据规模有点大，用搜索会MLE(即使开了个开栈挂
#pragma comment(linker, "/STACK:16777216") //for c++ Compiler #include <stdio.h> #include <iostream> #include <fstream> #include <cstring> #include <cmath> #include <stack> #include <string> #include <map> #include <set> #include <list> #include <queue> #include <vector> #include <algorithm> #define Max(a,b) (((a) > (b)) ? (a) : (b)) #define Min(a,b) (((a) < (b)) ? (a) : (b)) #define Abs(x) (((x) > 0) ? (x) : (-(x))) #define MOD 1000000007 #define pi acos(-1.0) using namespace std; typedef long long ll ; typedef unsigned long long ull ; typedef unsigned int uint ; typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;} template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e-7 ; const int N = 1 ; const int M = 200000 ; const ll P = 10000000097ll ; const int INF = 0x3f3f3f3f ; string a; int b, n; bool flag = false; string Multiply(string s,int x) //大数乘以整形数 { reverse(s.begin(),s.end()); int cmp=0; for(int i=0;i<s.size();i++) { cmp=(s[i]-‘0‘)*x+cmp; s[i]=(cmp%10+‘0‘); cmp/=10; } while(cmp) { s+=(cmp%10+‘0‘); cmp/=10; } reverse(s.begin(),s.end()); return s; } string Except(string s,int x) //大数除以整形数 { int cmp=0,ok=0; string ans=""; for(int i=0;i<s.size();i++) { cmp=(cmp*10+s[i]-‘0‘); if(cmp>=x) { ok=1; ans+=(cmp/x+‘0‘); cmp%=x; } else{ if(ok==1) ans+=‘0‘; //注意这里啊。才找出错误 } } return ans; } void dfs(string a, int len){ if(flag) return; if(n == len){ cout << a << endl; flag = true; return; } for(int i = 0; i < 10; ++i){ string num = a; num.push_back(‘0‘ + i); string nn = Except(num, b); string aa = Multiply(nn, b); if(aa.compare(num) == 0){ dfs(num, len + 1); } } } int main(){ int i, j, k, t, m, numCase = 0; //string hh = "123"; //cout << atoi(hh.c_str()); while(cin >> a >> b >> n){ dfs(a, 0); if(!flag){ cout << "-1" << endl; } } return 0; }
解题思路：
非常巧妙，就是先在a后面加一个数字0-9如果能整除b，那么易得an后面跟无论多少个0都能整除b
所以就在an后面构造出(n-1)个0即可
无须搜索，超过30层容易爆空间~
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler #include <stdio.h> #include <iostream> #include <fstream> #include <cstring> #include <cmath> #include <stack> #include <string> #include <map> #include <set> #include <list> #include <queue> #include <vector> #include <algorithm> #define Max(a,b) (((a) > (b)) ? (a) : (b)) #define Min(a,b) (((a) < (b)) ? (a) : (b)) #define Abs(x) (((x) > 0) ? (x) : (-(x))) #define MOD 1000000007 #define pi acos(-1.0) using namespace std; typedef long long ll ; typedef unsigned long long ull ; typedef unsigned int uint ; typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;} template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e-7 ; const int N = 1 ; const int M = 200000 ; const ll P = 10000000097ll ; const int INF = 0x3f3f3f3f ; int main(){ int i, j, k, t, n, m, numCase = 0; int a, b, num; //string hh = "123"; //cout << atoi(hh.c_str()); while(cin >> a >> b >> n){ bool flag = false; for(i = 0; i < 10; ++i){ num = a * 10 + i; if(num % b == 0){ a = num; flag = true; break; } } if(!flag){ cout << -1 << endl; return 0; } cout << num; for(i = 1; i < n; ++i) cout << ‘0‘; cout << endl; } return 0; }
原文：http://www.cnblogs.com/wushuaiyi/p/4282678.html
