найти количество делителей не знаю, что происходит не так

Я кодирую, чтобы найти число общих делителей двух чисел 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;
}

3

Решение

Вы сталкиваетесь с целочисленными переполнениями — i*i только безопасно до i=46340 (~ 2 ^ 15 * sqrt (2)) с 32-битными целыми числами, например:

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

Это приводит к неопределенному поведению.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]