醉了
这题在能力范围内。
思路、方向都想对了。但是最后统计答案时的细节没想好,醉了!!!
一直卡在最后统计答案上面。该说是没有手感吗?该说是生疏吗?
艹!!
本来能上不少分的!!
艹!!
来说思路吧!!
我数论不会,所以这题在我看到gcd、lcm的时候心里一凉。
并没有打算用数学的方法去解。
我是达标规律做的。
我打了1到300所有数,在1到300范围内的临近数们。
这一打表,我就找到规律了。
对于数num = a * b^2 令b最大
他等价于 a
所以,我们最初都可以进行数的简化
又然后,在进行合并的过程中。
对于一群同类数进行合并时,我们可以看到最终会变为a^k * c^2
c = b1b2b3......
如果k为偶数那么,就变为了1 * c^2
就永远变成了1的同类项
如果为奇数就变为了a*c^2
即不变。
所以,我们找到了规律。按照这个规律做就可以了。
我是利用筛法求解每一个数的本质的。
对每一个数进行暴力求解的话是会超时的!!!
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #include<cmath> using namespace std; typedef long long ll; const int max_n = 3e5+100; int b[max_n*4]; int a[max_n]; ll n,q; int main(){ ios::sync_with_stdio(0); for (int i=1;i<=1000;++i) for (int j=i*i;j<=1000000;j+=i*i) b[j]=j/(i*i); int t;cin>>t; while(t--){ cin>>n; for (int i=1;i<=n;++i)cin>>a[i],a[i]=b[a[i]]; sort(a+1,a+1+n); vector<int> v;v.push_back(1); for (int i=2;i<=n;++i){ if (a[i]==a[i-1]){ v.back()++; }else v.push_back(1); } int ans1=0,ans2=0; for (int ans : v)ans1=max(ans1,ans); for (int ans : v)if (ans%2==0)ans2+=ans; if (a[1]==1&&v[0]%2!=0)ans2+=v[0]; for (int ans : v)if (ans&1)ans2=max(ans2,ans); cin>>q; while (q--){ ll w;cin>>w; if (w==0)cout<<ans1<<endl; else cout<<ans2<<endl; } } }