QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#596570 | #5006. Heximal | PonyHex | WA | 1ms | 3724kb | C++20 | 4.4kb | 2024-09-28 16:01:10 | 2024-09-28 16:01:15 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define ll long long
#define double long double
#define lc u<<1
#define rc u<<1|1
#define X first
#define Y second
#define endl "\n"
//#define int long long
const int N = 2e5 + 50;
const int M = 5e5 + 5;
const ll maxm = 1e18 + 5;
const ll mod = 998244353;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
//random_shuffle(id + 1, id + n + 1);
ll ksm(ll a, ll b);
ll gcd(ll a, ll b);
template<class T>inline void read(T& x) {
x = 0;
char c = getchar();
while (!isdigit(c))c = getchar();
while (isdigit(c))x = x * 10 + (c & 15), c = getchar();
}
void write(ll x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
string str;
void solve()
{
//两个月前没有思路,两个月后依然没有,好像有?
//长度5e5,
//先考虑是否能通过ksm取模然后乘逆元获取ans
//或者,使用log函数,但是不支持加减分裂计算,再换方法,如果高精度的话感觉得超时
//题解py但是,我逛了圈qoj,发现了有c++出法,并且使用了log()/log(6)来转换成log6(),跟我思路一样,狂喜
//但是我没想到怎么实现
cin >> str;
ll len = str.size();
if (str == "0") {
cout << 1 << endl; return;
}
ll res = 0, ans = 0;
if (len <= 18) {
for (int i = 0; i < len; i++)res = res * 10 + (str[i] - '0');
ans = log10((double)res) / log10((double)6) + 1;//还有0位
}
else {
//关键来了,
for (int i = 0; i < 18; i++) res = res * 10 + str[i] - '0';
//这是先取了最高的18位元素
//woc,你过关,后面我们不管了,就直接认为是0,这样一来,就是长度(log后)
ans = (log10((double)res) + len - 18) / log10(6) + 1;
/*
for (int i = 0; i < len; i++) tmp = (tmp * 10 + str[i] - '0') % 21936950640377856ll;
if (tmp < 1e9) ++ans;*/
//上面的都看懂了,但是最后这个处理没看懂,从这个处理来看,大概是不能完全忽视影响
//哎哎,就是会差1,为什么只会差1,而且这个处理也看不懂
//看不懂好,我自己想办法,现在我知道后面的元素应该处理一下
//先处理出原来的元素会mod多少次,然后向上去试探,先比较mod数,再比较模值
//我们使用ksm实现
/*
ll base_cnt_mod = 0;
ll re = 0, base_val_mod = 0;
for (int i = 0; i < len; i++) {
re = re * 10 + (str[i] - '0');
base_cnt_mod *= 10;
base_cnt_mod %= 10;
if (re >= mod) {
re %= mod; base_cnt_mod++;
}
}
base_val_mod = re;
//while (1) {
ans++; re = 1;
ll try_cnt_mod=0;
ll try_val_mod=0;
//感觉就是1e5的跑法,怎么会t
//不对,本身就是不对的,这样跑完,mod时mod的数据获得的是*6而之前是*10
for (int i = 1; i <= ans; i++) {
re = re * 6;
try_cnt_mod *= 6;
try_cnt_mod %= mod;
if (re >= mod) {
re %= mod; try_cnt_mod++;
}
}
try_val_mod = re;
if (try_cnt_mod > base_cnt_mod) {
ans--; //break;
}
if (try_cnt_mod == base_cnt_mod) {
if (try_val_mod > base_val_mod) {
ans--; //break;
}
}
if (ans == 123576) {
cout << base_cnt_mod << " " << base_val_mod << " " << try_cnt_mod << " " << try_val_mod << endl;
}*/
//}
//这不行,我光脑测,mod的操作次数差距依然很大,超出mod限制后大小就变得无法比较
//再换,或许使用log来搞可以判定.不行,log对于内部是加减的情况无法处理,又回去了
//仅仅是
//没事,我还有法子,我们把原来的元素看做是log()=len+一个可算的小数
//然后check一下加1的ans
double mid1 = 0;
for (int i = len - 1; i >= 0; i--) {
mid1 = mid1 / 10 + str[i] - '0';
}
mid1 = log(mid1);
mid1 += len;
ans++; double mid2 = (double)ans * (log((double)6));
if (mid2 > mid1)ans--;
}
cout << ans << endl;
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
//cin >> T;
//read(T);
while (T--)
solve();
return 0;
}
/*PonyHex*/
ll ksm(ll a, ll b) {
ll base = a;
ll ans = 1;
while (b) {
if (b & 1)ans *= base % mod;
ans %= mod;
base *= base; base %= mod;
b >>= 1;
}
return ans % mod;
}
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
input:
0
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1865
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
6
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
5
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
216
output:
4
result:
ok single line: '4'
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3724kb
input:
659048550435237232393875796171343597297252783860791224966151609834498375660891507785647188078990198766575546966667938541517709208360385263203130845215396367798902376853652489767206051858708602045962531467486884777174160264291462611744982439094276291073422016146183934443085743192727084631329374278797...
output:
123576
result:
wrong answer 1st lines differ - expected: '123577', found: '123576'