QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692506 | #9307. Clock Master | qinglu09# | TL | 0ms | 0kb | C++23 | 1.9kb | 2024-10-31 14:38:13 | 2024-10-31 14:38:37 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> PLL;
#define endl '\n'
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const ll N = 30001;
#define debug(x) cout<<#x<<": "<<x<<endl
long double dp[N][3246], ans[N], lg[N];
ll siz;
bool vis[N];
int prime[N];//0是质数
vector<int>d;
void init_prime()
{
vis[1] = 1;
for(int i = 2; i < N; i++)
{
if(!vis[i])
{
prime[++prime[0]] = i;
d.push_back(i);
}
for(int j = 1; i * prime[j] < N; j++)
{
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
void dfs()
{
per(i, N - 1, 0)
{
rep(j, 0, siz - 1)
{
ll cur = d[j];
while(1)
{
if(cur > i) break;
dp[i - cur][j + 1] = max(dp[i - cur][j + 1], dp[i][j] + lg[cur]);
cur *= d[j];
}
}
}
}
void solve()
{
ll x;
cin >> x;
cout << fixed << setprecision(9) << ans[x] << endl;
// rep(i, 1, N - 1)
// {
// cout << "," << fixed << setprecision(9) << ans[i];
// }
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll T=1;
init_prime();
siz = d.size();
lg[0] = 0;
rep(i, 1, N - 1)
{
lg[i] = log(i);
}
// cout << siz << endl;;
dfs();
rep(i, 1, N - 1)
{
rep(j, 0, siz - 1)
{
ans[i] = max(ans[i], dp[N - 1- i][j]);
}
}
cin>>T;
while(T--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 7 10