素因子集合

題目詳情:

小強(qiáng)最近在學(xué)初等數(shù)論，老師給他們出了一個(gè)課后習(xí)題，那就是給你兩個(gè)正整數(shù)A，B（0<A,B<2^60）,判斷他們的素因子集合是否相同，小強(qiáng)剛接觸數(shù)論，想了好一會(huì)還是沒(méi)能想出來(lái)，你能幫助他嗎？

輸入描述：

輸入包含多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)包含兩個(gè)正整數(shù)A，B,以文件結(jié)束。

輸出描述：

對(duì)于每組測(cè)試數(shù)據(jù)如果A和B的素因子集合相同則輸出“YES”，否則輸出“NO”。

答題說(shuō)明:

輸入樣例：

2 8

4 9

10 50

輸出樣例：

YES

NO

YES

AC碼：

#include<stdio.h> #include<string.h> long long num1[200000],num2[200000]; long long Euler(long long n,long long num[]) {long long i,k=0;for(i=2;i*i<=n;i++){if(n%i==0){num[k++]=i;while(n%i==0)n/=i;}}if(n>1){num[k++]=n;}return k; } int main() {long long a,b,x,y,i;while(~scanf("%lld%lld",&a,&b)){memset(num1,0,sizeof(num1));memset(num2,0,sizeof(num2));x=Euler(a,num1);y=Euler(b,num2);if(x==y){for(i=0;i<x;i++){if(num1[i]!=num2[i])break;}if(i>=x)printf("YES\n");elseprintf("NO\n");}elseprintf("NO\n");}return 0; }
AC碼：

#include<stdio.h> #include<string.h> __int64 num1[200000],num2[200000]; __int64 Euler( __int64 n, __int64 num[200000]) {int i,k=0;for(i=2;i*i<=n;i++){if(n%i==0){num[k++]=i;while(n%i==0)n/=i;}}if(n>1){num[k++]=n;}return k; } int main() {__int64 a,b,x,y,i;while(~scanf("%I64d %I64d",&a,&b)){memset(num1,0,sizeof(num1));memset(num2,0,sizeof(num2));x=Euler(a,num1);y=Euler(b,num2);if(x==y){for(i=0;i<x;i++){if(num1[i]!=num2[i])break;}if(i>=x)printf("YES\n");elseprintf("NO\n");}elseprintf("NO\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的素因子集合的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。