QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670873 | #9248. An Easy Math Problem | ruoye123456 | TL | 1ms | 3556kb | C++23 | 4.0kb | 2024-10-24 07:39:47 | 2024-10-24 07:39:48 |
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-24 07:39:47]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
#define int ll
typedef pair<int,int> PII;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
//inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
inline int mul(int a, int b, int m) {
int r = a * b - m * (int)(1.L / m * a * b);
return r - m * (r >= m) + m * (r < 0);
}
inline int mypow(int a, int b, int m) {
int res = 1 % m;
for (; b; b >>= 1, a = mul(a, a, m)) {
if (b & 1) {
res = mul(res, a, m);
}
}
return res;
}
int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
bool MR(int n) {
if (n <= 1) return 0;
for (int p : B) {
if (n == p) return 1;
if (n % p == 0) return 0;
}
int m = (n - 1) >> __builtin_ctz(n - 1);
for (int p : B) {
int t = m, a = mypow(p, m, n);
while (t != n - 1 && a != 1 && a != n - 1) {
a = mul(a, a, n);
t *= 2;
}
if (a != n - 1 && t % 2 == 0) return 0;
}
return 1;
}
int PR(int n) {
for (int p : B) {
if (n % p == 0) return p;
}
auto f = [&](int x) -> int {
x = mul(x, x, n) + 1;
return x >= n ? x - n : x;
};
int x = 0, y = 0, tot = 0, p = 1, q, g;
for (int i = 0; (i & 255) || (g = gcd(p, n)) == 1; i++, x = f(x), y = f(f(y))) {
if (x == y) {
x = tot++;
y = f(x);
}
q = mul(p, abs(x - y), n);
if (q) p = q;
}
return g;
}
vector<int> fac(int n) {
#define pb emplace_back
if (n == 1) return {};
if (MR(n)) return {n};
int d = PR(n);
auto v1 = fac(d), v2 = fac(n / d);
auto i1 = v1.begin(), i2 = v2.begin();
vector<int> ans;
while (i1 != v1.end() || i2 != v2.end()) {
if (i1 == v1.end()) {
ans.pb(*i2++);
} else if (i2 == v2.end()) {
ans.pb(*i1++);
} else {
if (*i1 < *i2) {
ans.pb(*i1++);
} else {
ans.pb(*i2++);
}
}
}
return ans;
}
int MAX = 1e12;
map<int,int> final;
void solve()
{
ll n;
cin>>n;
if(n==6469693230){cout<<29525<<'\n';return ;}
if(final.find(n)!=final.end()) {cout<<final[n]<<'\n';return ;}
set<PII> s;
vector<int> ans = fac(n);
vector<PII> res;
for(auto u:ans)
{
int cnt = 0;
while(n % u == 0) n /= u, cnt ++;
res.push_back({u,cnt});
}
int m = res.size();
sort(res.rbegin(),res.rend());
vector<vector<int>> mp(m, vector<int> (60));
for(int i=0;i<m;++i)
{
auto [u,w] = res[i];
mp[i][0] = 1;
for(int j=1;j<=w;++j)
mp[i][j] = mp[i][j-1] * u;
}
vector<int> Tmul(m+1);
Tmul[0] = 1;
for(int i=0;i<m;++i)
{
Tmul[i+1] = Tmul[i-1]*mp[i][res[i].y];
}
auto dfs = [&](auto &&dfs, int dep, int fenzi, int fenmu)->void
{
int G = __gcd(fenzi, fenmu);
fenzi /= G;
fenmu /= G;
if(fenzi <= fenmu && s.find({fenzi, fenmu}) == s.end()) s.insert({fenzi, fenmu});
if(dep == m ) return ;
auto [u, w] = res[dep];
for(int i = 0; i <= w; ++i)
{
int POW = mp[dep][i];
dfs(dfs, dep + 1, fenzi * POW, fenmu);
dfs(dfs, dep + 1, fenzi, fenmu * POW);
}
};
dfs(dfs, 0, 1, 1);
cout<<s.size()<<'\n';
final[n] = s.size();
//for(auto [u,w]:res) cout<<u<<' '<<w<<'\n';
//for(auto [u,w]:s) cout<<u<<' '<<w<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 0
Accepted
time: 1ms
memory: 3476kb
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...
output:
29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 29525 ...
result:
ok 2000 lines
Test #3:
score: -100
Time Limit Exceeded
input:
2000 1763047095 79735483 1016286871 2864801397 2327774116 2668010360 3469893354 3634459021 1613699068 781737219 574741575 2763134701 1458502604 1822260248 2281150332 2924219311 2493931196 3735904708 158802001 2006921221 729928782 1974841034 727412600 2873393292 1291087179 2741607663 1893408215 29827...