75
技術社區[雲棲]
uva 10624 Super Number 回溯
暴力回溯，用位運算加個奇偶剪枝
注意取餘的效率，因為取餘實在太慢了，所以要最少的進行取餘運算，所以就是每19位進行次取餘，這樣1s內就過了
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <stdio.h>
int ans[50];
char nok(int now)
{
int i,t;
unsigned long long r;
for(i=r=t=0;i<now;i++,t++)
{
r=r*10+ans[i];
if(t==18)//19位
{
t=0;
r%=now;
}
}
return r%now;
}
int n,m;
char dfs(int now)
{
if(now>m)return 1;
int i=(now==1),f=now&1,t=now-1;
for(;i<10;i++)
{
ans[t]=i;
if(now>=n&&((!f&&(i&1))||nok(now)))continue;//奇偶
if(dfs(now+1))return 1;
}
return 0;
}
int main()
{
int T,C=0;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
printf("Case %d: ",++C);
if(!dfs(1))printf("-1\n");
else
{
int i;
for(i=0;i<m;i++)
printf("%d",ans[i]);
puts("");
}
}
}
最後更新：2017-04-04 07:03:48