样例没过却ac(doge)
查看原帖
样例没过却ac(doge)
1213719
Algorithm_king楼主2024/11/20 20:15

数据过水,代码如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,t,cnt;
ll tmin=0x7fffffffffffffff,a[105],c[105],fz[105],fm[105];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>c[i]; 
	sort(c+1,c+n+1);
	for(int i=1;i<=n;i++)
		if(c[i]!=c[i-1])
			a[++cnt]=c[i];
	for(int i=1;i<cnt;i++)
		{
			ll t=__gcd(a[i],a[i+1]);
			fz[i]=a[i+1]/t,fm[i]=a[i]/t;
		}
	for(int i=1;i<cnt;i++)
		if(tmin>fz[i])
			t=i,tmin=fz[i];
	ll ans1=tmin,ans2=fm[t],f=0;
	if(ans2==1)
		{
			sort(fz+1,fz+cnt);
			cout<<fz[1]<<'/'<<1;
			return 0;
		}
	for(int i=1;i<cnt;i++)
		{
			ll x=fz[i],y=fm[i];
			int cnt1=0,cnt2=0;
			while(x%ans1==0) cnt1++,x/=ans1;
			while(y%ans2==0) cnt2++,y/=ans2;
			if(cnt1!=cnt2||(x!=1&&y!=1)) 
				{
					f=1;
					break;
				}
		}
	if(!f)
		{
			cout<<ans1<<'/'<<ans2;
			return 0;
		}
	for(int i=2;i*i<=fz[t];i++)
		{
			if(fz[t]%i==0)	
				{
					int cnt=0;
					ll g=fz[t];
					//cout<<i<<endl;
					while(g%i==0)
						{
							cnt++;
							//cout<<cnt<<endl;
							g/=i;
						}
					for(int j=1;pow(j,cnt)<=fm[t];j++)
						if(pow(j,cnt)==fm[t])
							{		
								cout<<i<<'/'<<j;
								return 0;
							}
				}
		}
	return 0;
}```
2024/11/20 20:15
加载中...