Я кодирую, чтобы найти число общих делителей двух чисел 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;
}
Вы сталкиваетесь с целочисленными переполнениями — i*i
только безопасно до i=46340
(~ 2 ^ 15 * sqrt (2)) с 32-битными целыми числами, например:
i i*i
46339 2147302921
46340 2147395600
46341 -2147479015
46342 -2147386332
Это приводит к неопределенному поведению.
Других решений пока нет …