QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #517 | #310338 | #8000. 平方数 | Qingyu | masterhuang | Failed. | 2024-01-21 23:05:12 | 2024-01-21 23:05:13 |
詳細信息
Extra Test:
Accepted
time: 352ms
memory: 53088kb
input:
300000 11451419198100000000000000000000000 11451419198100000000000000000000001 11451419198100000000000000000000002 11451419198100000000000000000000003 11451419198100000000000000000000004 11451419198100000000000000000000005 11451419198100000000000000000000006 11451419198100000000000000000000007 11451...
output:
1148390 71924 71924 71924 71925 71924 71926 71924 71927 71924 71928 71924 71929 71924 71930 71924 71931 71924 71932 71924 71933 71924 71934 71924 71935 71924 71936 71924 71937 71924 71938 71924 71939 71924 71940 71925 71925 71925 71926 71925 71927 71925 71928 71925 71929 71925 71930 71925 71931 7192...
result:
ok 200001 numbers
| 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;
}