QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #515 | #310954 | #8000. 平方数 | Qingyu | perspective | Success! | 2024-01-21 22:13:01 | 2024-01-21 22:13:01 |
详细
Extra Test:
Wrong Answer
time: 107ms
memory: 41784kb
input:
300000 11451419198100000000000000000000000 11451419198100000000000000000000001 11451419198100000000000000000000002 11451419198100000000000000000000003 11451419198100000000000000000000004 11451419198100000000000000000000005 11451419198100000000000000000000006 11451419198100000000000000000000007 11451...
output:
1639270 73448 226536 73448 226537 73448 226538 73448 226539 73448 226540 73448 226541 73448 226542 73448 226543 73448 226544 73448 226545 73448 226546 73448 226547 73448 226548 73448 226549 73448 226550 73448 226551 73448 226552 73448 226553 73449 73449 73449 73450 73449 73451 73449 73452 73449 7345...
result:
wrong answer 1st numbers differ - expected: '1639252', found: '1639270'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #310954 | #8000. 平方数 | perspective | 95 | 151ms | 64064kb | C++14 | 1.2kb | 2024-01-21 20:00:14 | 2024-01-21 22:13:42 |
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef __int128 L;
typedef unsigned long long ull;
const int N=3e5+5,M=1e5+5;
int n,num; L a[N];
ull b[N],ans; bool vis[M],ok[M];
__gnu_pbds::gp_hash_table<ull,int> id;
vector<int> vec[N]; mt19937 rnd(time(0));
inline void read(L &ret){
ret=0; int ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch))
ret=ret*10+(ch^48),ch=getchar();
}
int main(){
cin>>n,vis[1]=1;
for(int i=1;i<=n;++i) read(a[i]);
for(int i=2;i<M;++i){
if(vis[i]) continue;
for(int j=i*2;j<M;j+=i) vis[j]=1;
}
for(int t=0,p;t<38;++t){
while(1){
p=rnd()%(M-1)+1;
if(!vis[p]) break;
}
memset(ok,0,sizeof(ok));
for(int i=1;i<=(p+1)/2;++i) ok[1ll*i*i%p]=1;
for(int i=1,s=0;i<=n;++i){
L x=a[i]; while(x%p==0) x/=p;
s^=!ok[x%p],b[i]^=s*(1ull<<t);
}
}
for(int i=0;i<=n;++i){
if(!id[b[i]]) id[b[i]]=++num;
vec[id[b[i]]].emplace_back(i);
}
for(int i=1;i<=num;++i)
ans+=1ll*vec[i].size()*(vec[i].size()-1)/2;
cout<<ans<<endl,ans=min(ans,100000ull);
for(int l=1;l<=n&&ans;++l){
int x=id[b[l-1]];
for(int r:vec[x])
if(l<=r){
printf("%d %d\n",l,r);
if(!(--ans)) break;
}
}
return 0;
}