3

私は2つの数nとkの最大公約数を見つけるためにコーディングしています。

GCD gを見つけてから、GCDの約数の数を見つけるというアプローチを使用して実装しています。

ただし、コードはコンパイルされますが、実行時に応答しないメッセージが表示されます:(

私はこれに頭を悩ませました..誰かがデバッグを手伝ってくれますか..よろしくお願いします

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>

using namespace std;

vector<bool>p(1000002,true);

long int getgcd(long int a, long int b)
{  if(b == 0)
          return a;
   else
          return getgcd(b, a % b);
}

void prime()
{   int i,j;
    for(i=2;i<1000001;i++)
      if(p[i])
        for(j=i*i;j<1000001;j=j+i)
             p[j]=false;
    p[0]=false;
    p[1]=false;
}

void divfind(long int a, long int b)
{
     long int g;
     g = getgcd(a,b);
     int i,s,j=0,ans=1,num=0;
     //short int fo[1000000];
     s=(int) sqrt(g);
     for(i=2;i<s+1;i++)
       if(p[i])
        {
          while(g%i==0)
          {g=g/i;
           num++;
          }
          if(num)
            ans*=++num;
          num=0;
        }
      printf("%d\n",ans);
}

int main()
{
    prime();
    long int n;
    int q;
    scanf("%ld %d",&n,&q);
    while(q--)
    {
        int t;
        long int k;
        scanf("%d%ld",&t,&k);
        if(t==1)
        divfind(n,k);
//        else if(t==2)
//       divi(n,k);
//        else
//        nodivi(n,k);
    }
    return 0;
}
4

1 に答える 1

2

整数のオーバーフローが発生しています-32ビット整数の場合は（〜2 ^ 15 * sqrt（2））i*iまでしか安全ではありません。例：i=46340

i     i*i
46339 2147302921
46340 2147395600
46341 -2147479015
46342 -2147386332

これは未定義の動作につながります。

于 2012-09-04T19:53:11.110 に答える