CodeForces 260A Adding Digits

这道题目的意思是给你提供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-      ;

const int N =               ;

const int M =          ;

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=;

    for(int i=;i<s.size();i++)

    {

        cmp=(s[i]-'')*x+cmp;

        s[i]=(cmp%+'');

        cmp/=;

    }

    while(cmp)

    {

        s+=(cmp%+'');

        cmp/=;

    }

    reverse(s.begin(),s.end());

    return s;

}

string Except(string s,int x)  //大数除以整形数

{

    int cmp=,ok=;

    string ans="";

    for(int i=;i<s.size();i++)

    {

        cmp=(cmp*+s[i]-'');

        if(cmp>=x)

        {

            ok=;

            ans+=(cmp/x+'');

            cmp%=x;

        }

        else{

            if(ok==)

                ans+='';  //注意这里啊。才找出错误

        }

    }

    return ans;

}

void dfs(string a, int len){

    if(flag)    return;

    if(n == len){

        cout << a << endl;

        flag = true;

        return;

    }

    for(int i = ; i < ; ++i){

        string num = a;

        num.push_back('' + i);

        string nn = Except(num, b);

        string aa = Multiply(nn, b);

        if(aa.compare(num) == ){

            dfs(num, len + );

        }

    }

}

int main(){

    int i, j, k, t, m, numCase = ;

    //string hh = "123";

    //cout << atoi(hh.c_str());

    while(cin >> a >> b >> n){

        dfs(a, );

        if(!flag){

            cout << "-1" << endl;

        }

    }

    return ;

}

MLE Code

解题思路：

非常巧妙，就是先在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-      ;

const int N =               ;

const int M =          ;

const ll P = 10000000097ll   ;

const int INF = 0x3f3f3f3f   ;

int main(){

    int i, j, k, t, n, m, numCase = ;

    int a, b, num;

    //string hh = "123";

    //cout << atoi(hh.c_str());

    while(cin >> a >> b >> n){

            bool flag = false;

            for(i = ; i < ; ++i){

                num = a *  + i;

                if(num % b == ){

                    a = num;

                    flag = true;

                    break;

                }

            }

            if(!flag){

                cout << - << endl;

                return ;

            }

        cout << num;

        for(i = ; i < n; ++i) cout << '';

        cout << endl;

    }

    return ;

}