hdu4393Digital Square（dfs）

15-10-19 来源：[db:作者]

收藏我要投稿

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<

点击复制链接与好友分享!回本站首页