RT, 这是我最开始提交的代码,它获得了 95 pts(提交记录):
#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 1e5 + 10, M = 1e7 + 10;
int pri[M / 10], minp[M], tot;
bool vis[M];
il void euler(int n)
{
vis[0] = vis[1] = 1;
for(int i = 2;i <= n;++i)
{
if(!vis[i]) pri[++tot] = i, minp[i] = i;
for(int j = 1;pri[j] <= n / i;++j)
{
vis[i * pri[j]] = 1;
minp[i * pri[j]] = pri[j];
if(i % pri[j] == 0) break;
}
}
}
int f[N], a[N], n;
map<set<int>, int> mp;
map<set<int>, bool> tag;
set<int> s;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
euler(1e7);
cin >> n;
for(int i = 1;i <= n;++i) cin >> a[i];
int ans = 0;
for(int i = 1;i <= n;++i)
{
s.clear();
int x = a[i];
while(x > 1)
{
int y = minp[x], cnt = 0;
while(x % y == 0) x /= y, cnt++;
if(cnt & 1) s.insert(y);
}
if(!tag.count(s))
{
if(s.empty()) f[i] = 1;
else f[i] = 0;
}
else
{
if(s.empty()) f[i] = mp[s] + 1;
else if(mp[s] == 0) f[i] = mp[s] + 2;
else f[i] = mp[s] + 1;
}
mp[s] = max(mp[s], f[i]);
tag[s] = 1;
ans = max(ans, f[i]);
}
cout << ans;
return 0;
}
但是我把 ans 的初始化从 0 改成 1 就通过了(提交记录)
我认为两者代码的区别当且仅当以下数据(即 n=1 加上一个非完全平方数)
1
2
这个输出应该是 0,AC 程序输出的是 1,95 程序输出是 0。
请问是我的程序有 bug 还是数据锅了?
求助,违规紫衫