QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #518 | #310338 | #8000. 平方数 | Qingyu | masterhuang | Success! | 2024-01-22 00:28:36 | 2024-01-22 00:28:36 |
詳細信息
Extra Test:
Wrong Answer
time: 387ms
memory: 52412kb
input:
300000 11451419198100000000000000000000000 11451419198100000000000000000000001 11451419198100000000000000000000002 11451419198100000000000000000000003 11451419198100000000000000000000004 11451419198100000000000000000000005 11451419198100000000000000000000006 11451419198100000000000000000000007 11451...
output:
314326 71337 228657 71337 228658 71337 228659 71337 228660 71337 228661 71337 228662 71337 228663 71340 71340 71340 71341 71341 71341 71343 71343 71343 71344 71343 71345 71343 71346 71343 71347 71343 71348 71344 71344 71344 71345 71344 71346 71344 71347 71344 71348 71345 71345 71345 71346 71345 7134...
result:
wrong answer 1st numbers differ - expected: '314319', found: '314326'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #310338 | #8000. 平方数 | masterhuang | 97 | 530ms | 90968kb | C++20 | 1.5kb | 2024-01-21 11:24:50 | 2024-01-22 00:29:00 |
answer
//洛谷 P10063
//https://www.luogu.com.cn/problem/P10063
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define LL long long
#define ull unsigned long long
#define bll __int128
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(time(0));
const int N=3e5+5,B=50;
inline bll rd()
{
bll x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int n,b[N],pr[N],tot,e[N];ull d[N],ans;bool v[N*4];bll a[N];
gp_hash_table<ull,vector<int>>mp;
inline void init(int M=1e6)
{
for(int i=2;i<=M;i++)
{
if(!v[i]) pr[++pr[0]]=i;
for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++)
{
v[i*pr[j]]=1;
if(i%pr[j]==0) break;
}
}int cnt=0;
for(int i=1;i<=pr[0];i++) if(5e5<=pr[i]&&pr[i]<=1e6) b[++cnt]=pr[i];
shuffle(b+1,b+1+cnt,rnd);
}
inline void get(int t)
{
const unsigned mod=b[t];fill(v+0,v+1+mod,1);
for(int i=0;i<mod;i++) v[1ll*i*i%mod]=0;
for(int i=1;i<=n;i++)
{
bll x=a[i];while(x%mod==0) x/=mod;
if(v[x%mod]) d[i]|=(1ll<<t);
}
}
int main()
{
init();scanf("%d",&n);for(int i=1;i<=n;i++) a[i]=rd();
for(int i=1;i<=B;i++) get(i);
for(int i=1;i<=n;i++) d[i]^=d[i-1];
for(int i=0;i<=n;i++) mp[d[i]].push_back(i),e[i]=mp[d[i]].size();
for(int i=0;i<n;i++) ans+=mp[d[i]].size()-e[i];printf("%llu\n",ans);
for(int i=0;i<n;i++)
{
vector<int>g=mp[d[i]];
for(int j=e[i];j<g.size();j++){printf("%d %d\n",i+1,g[j]);if(++tot==1e5) return 0;}
}
return 0;
}