QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139601 | #2058. Generator | As3b_team_f_masr# | ML | 0ms | 0kb | C++14 | 1.2kb | 2023-08-14 01:27:12 | 2023-08-14 01:27:15 |
answer
#include <bits/stdc++.h>
#define F first
#define S second
#define ld long double
#define EPS 1e-9
using namespace std;
typedef long long ll;
const int N = 1e7+5;
int a[N],sq[N],mn[N];
int p[N],cnt[N];
bool pr[N];
ll pre1[N],pre2[N];
void solve(ll ne,ll de)
{
ll g=__gcd(ne,de);
cout<<ne/g<<"/"<<de/g<<'\n';
}
int main ()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//freopen("wigz.in","r",stdin);
for(int i=2;i<N;i++)
{
if(!p[i])
{
pr[i]=1;
for(int j=i;j<N;j+=i)
{
if(p[j])continue;
p[j]=i-1;
}
}
}
for(int i=2;i*i<N;i++)
{
sq[i*i]=i-1;
}
for(int i=2;i<N;i++)
{
sq[i]=max(sq[i-1],sq[i]);
mn[i]=min(sq[i],p[i]);
cnt[i]=pr[i];
cnt[i]+=cnt[i-1];
if(pr[i])pre1[i]+=mn[i];
else pre2[i]+=mn[i];
pre1[i]+=pre1[i-1];
pre2[i]+=pre2[i-1];
}
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
ll ne=pre1[n]+pre2[n];
ll de=cnt[n];
solve(ne,de);
}
return(0);
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
6 2 3 4 5 6 10