zoj 3609

比赛的时候卡在这里,都是我没有把题目看懂,m=1的情况没考虑好,直接当不存在处理了==

下面给一种暴力法

不过时间也是很快的

#include<iostream>
#include<cstdio>
using namespace std;


int t;
int main()
{
    int t,a,m,aa,ans,mm,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&m);
        if(m==1||a==1)
        {
            printf("1\n");
            continue;
        }
        if(a%m==0||m%a==0)
        {
            printf("Not Exist\n");
            continue;
        }
        for(i=1;i<m;i++)
        {
            if(a*i%m==1)
            {
                break;
            }
        }
        if(i==m)
        {
            printf("Not Exist\n");
        }
        else
        {
            printf("%d\n",i);
        }
    }
    return 0;
}
 下面是我比赛时想的,因为m=1考虑出错,结果很悲剧
#include<iostream>
#include<cstdio>
using namespace std;

int run(int a,int b)
{
    if(a<b)
    {
        a^=b;
        b^=a;
        a^=b;
    }
    if(b==0) return a;
    return run(b,a%b);
}

int t;
int main()
{
    int t,a,m,aa,ans,mm;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&m);
        if(m==1||a==1)
        {
            printf("1\n");
            continue;
        }
        if(a%m==0||m%a==0)
        {
            printf("Not Exist\n");
            continue;
        }
        if(run(a,m)==1)
        {
            if(a>m)
            {
                aa=a;
                while(aa%m!=1)
                {
                    aa+=a;
                }
                ans=aa/a;
            }
            else
            {
                mm=m;
                while((mm+1)%a!=0)
                {
                    mm+=m;
                }
                ans=(mm+1)/a;
            }
            printf("%d\n",ans);
        }
        else
        {
            printf("Not Exist\n");
        }
    }
    return 0;
}






posted on 2012-04-15 18:52 煙雨默嘫 阅读(427) 评论(0)  编辑 收藏 引用 所属分类: c++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

公告

  • 默默的大神
  • 常用链接

    留言簿

    随笔分类

    随笔档案

    文章档案

    相册

    最新随笔

    搜索

    积分与排名

    最新评论

    阅读排行榜

    评论排行榜