http://acm.fjnu.edu.cn/show?problem_id=2034
純暴力會超時，先預(yù)處理把一些X中間的數(shù)合并
再二分
#include<stdio.h>
#include<ctype.h>
#include<string>
int b,cnt,len;
int ans[10];
char a[10001];
int num[20];
int weishu[20];
int Pow(int a,int b,int c)
{
int sum=1;
while(b)
{
if(b%2==0)
{
b /= 2;
a = (a*a)%c;
}
b --;
sum = (a*sum)%c;
}
return sum;
}
void dfs(int i,int k,int c)
{
int j;
for(;i<len;i++)
{
if(num[i]!=-1)
{
k = k + num[i]*Pow(10,weishu[i],b);
if(k>=b)
k %= b;
}
else
{
for(j=0;j<10;j++)
{
num[i] = j;
int d = cnt;
dfs(i,k,c+1);
if(d!=cnt)
ans[c] = j;
num[i] = -1;
}
return ;
}
}
if(k==0)
cnt ++;
}
void yuchuli()
{
int i;
int l = strlen(a);
len = 0;
int k = 0;
for(i=0;a[i];i++)
{
if(isdigit(a[i]))
{
k = k*10 + a[i]-'0';
if(k>=b)
k %= b;
}
else
{
if(k)
{
num[len] = k;
weishu[len] = l-i;
len ++;
k = 0;
}
num[len] = -1;
weishu[len] = l-i-1;
len ++;
}
}
if(k)
{
num[len] = k;
weishu[len] = l-i;
len ++;
}
}
int main()
{
while(scanf("%s%d",a,&b)==2)
{
yuchuli();
cnt = 0;
dfs(0,0,0);
if(cnt)
{
int j=0;
for(int i=0;a[i];i++)
{
if(isdigit(a[i]))
putchar(a[i]);
else
putchar(ans[j++]+'0');
}
printf("\n%d\n",cnt);
}
else
puts("POOR TT!");
}
return 0;
}
posted on 2009-03-19 16:12
shǎ崽 閱讀(596)
評論(0) 編輯 收藏 引用