Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1003K-CrashingBalloon-ZJU
发信站: 哈工大紫丁香 (2002年10月06日19:54:21 星期天), 站内信件

测试每个数是否能分解成100以内的整数的乘积
然后根据结果分类输出
只有两个都能分解的时候，判断有没有冲突
#include "stdafx.h"
#include "stdio.h"
#include "string.h"
int core=0;
int p1,p2;
int divt(char* flag,int N,int last,int pos)
{
    int i;
    if(N==1){core=1;return 0;}
    if(pos==100) return 0;
    if(N<last) return 0;
    for(i=last+1;i<=100;i++)
        if(N%i==0&&flag[i]>=1)
        {
            flag[i]=-1;
            divt(flag,N/i,i,pos+1);
            flag[i]=1;
        }
    return 0;
}
int div(char* flag,int N,int M,int last,int pos)
{
    int i;
    if(core==1) return 0;
    if(pos==100) return 0;
    if(N==1){divt(flag,M,1,0);return 0;}
    if(N<last) return 0;
    for(i=last+1;i<=100;i++)
        if(N%i==0)
        {
            flag[i]=0;
            div(flag,N/i,M,i,pos+1);
            flag[i]=1;
        }
    return 0;
}
int main(int argc, char* argv[])
{
    char flag[101];
    int k,N,M;
#ifndef ONLINE_JUDGE
    freopen("1003.in","r",stdin);
#endif
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        memset(flag,1,101);
        if(N<M) {k=M;M=N;N=k;}
        p1=p2=core=0;
        divt(flag,N,1,0);
        p1=core;
        core=0;
        memset(flag,1,101);
        divt(flag,M,1,0);
        p2=core;
        core=0;
        if(p1*p2)
        {
            memset(flag,1,101);
            div(flag,N,M,1,0);
            if(core) printf("%d\n",N);
            else     printf("%d\n",M);
        }
        else if(p1) printf("%d\n",N);
        else if(p2) printf("%d\n",M);
        else        printf("%d\n",N);
    }
    return 0;
}


--
猜谜语：太监以前有，进宫后没有；
和尚有但是不用，外国人比中国人的长。
打一人身上的东西？想歪了吧——是名字！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.231]