QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#656130 | #9248. An Easy Math Problem | Fiatiustitia# | TL | 1ms | 3888kb | C++20 | 2.2kb | 2024-10-19 11:28:33 | 2024-10-19 11:28:34 |
Judging History
This is the latest submission verdict.
- [2024-10-31 22:36:43]
- hack成功,自动添加数据
- (/hack/1098)
- [2024-10-31 22:13:58]
- hack成功,自动添加数据
- (/hack/1096)
- [2024-10-31 22:00:43]
- hack成功,自动添加数据
- (/hack/1095)
- [2024-10-19 11:28:33]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
vector<int> minp, prime;
void sieve(int n)
{
minp.resize(n + 1);
for (int i = 2; i <= n; i++)
{
if (!minp[i])
{
minp[i] = i;
prime.push_back(i);
}
for (auto p : prime)
{
if (p * i > n)
break;
minp[i * p] = p;
if (i % p == 0)
break;
}
}
}
vector<pair<long long, int>> p;
vector<int> q;
void dfs(int u, long long pre)
{
if (u == p.size())
{
q.push_back(pre);
return;
}
for (int i = 0; i <= p[u].second; i++)
{
dfs(u + 1, pre);
pre *= p[u].first;
// cout<<pre<<'\n';
}
}
void solve()
{
long long n;
cin >> n;
// n = 1e10;
long long tmp = n;
p.clear(), q.clear();
for (auto i : prime)
{
if (i > n / i)
break;
if (n % i == 0)
{
int cnt = 0;
while (n % i == 0)
{
cnt++;
n /= i;
}
p.push_back(make_pair(i, cnt));
}
}
if (n != 1)
{
p.push_back(make_pair(n, 1));
}
dfs(0, 1);
sort(q.begin(), q.end());
const int m = q.size();
// cout << q.size() << '\n';
// set<long long> se;
vector<int64_t> t;
for(int i = 0;i < m;i++)
{
for(int j = 0;j <= i;j++)
{
t.push_back(tmp / q[i] * q[j]);
}
}
sort(t.begin(),t.end());
t.resize(unique(t.begin(),t.end()) - t.begin());
// for (int i = 0; i < q.size(); i++)
// {
// // cout << q[i] << '\n';
// for (int j = 0; j <= i; j++)
// {
// se.insert(1ll * tmp / q[i] * q[j]);
// }
// }
cout << t.size() << '\n';
}
int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
auto _ = clock();
#endif
sieve(1e5 + 7);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
solve();
#ifdef LOCAL
cerr << clock() - _ << '\n';
#endif
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 2 3 2 5 2 4 3 5
result:
ok 10 lines
Test #2:
score: -100
Time Limit Exceeded
input:
2000 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 646969323...