程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu4393Digital Square（dfs）

hdu4393Digital Square（dfs）

編輯：關於C++

Digital Square

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1827 Accepted Submission(s): 714

Problem Description Given an integer N,you should come up with the minimum nonnegative integer M.M meets the follow condition: M²%10^x=N (x=0,1,2,3....)
Input The first line has an integer T( T< = 1000), the number of test cases.
For each case, each line contains one integer N(0<= N <=10⁹), indicating the given number.
Output For each case output the answer if it exists, otherwise print “None”.
Sample Input

Sample Output

None
11
5

Source 2012 Multi-University Training Contest 10
題意：求最小的M滿足M²%10^x=N (x=0,1,2,3....)。分析：從N的個位開始，一位一位的往上搜；即先個位，再十位，百位·····。

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define ll long long
#define CL(a) memset(a,0,sizeof(a))

ll n,k,ans;

ll dfs(ll pe, ll re)//pe表示當前最高位，re表示之前滿足條件的數
{
    if (pe > n) return 0;
    for (int i=0; i<10; i++)
    {
        ll a = i*pe+re;//最高位10種情況一次搜索
        ll aa = a*a%(pe*10);
        ll nn = n%(pe*10);
        if (aa == nn)
        {
            if (aa == n)
                ans = min(ans, a);
            else
                dfs(pe*10, a);//往上繼續搜索
        }
    }
    return 0;
}

int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        cin>>n;
        ans = INF;
        dfs(1, 0);//搜索只搜了1~999999999
        if (n==0)
        {
            cout<<0<