QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139601#2058. GeneratorAs3b_team_f_masr#ML 0ms0kbC++141.2kb2023-08-14 01:27:122023-08-14 01:27:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-14 01:27:15]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-08-14 01:27:12]
  • 提交

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

output:


result: