QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#596254#5006. HeximalPonyHexTL 0ms3796kbC++203.4kb2024-09-28 15:24:352024-09-28 15:24:43

Judging History

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

  • [2024-09-28 15:24:43]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3796kb
  • [2024-09-28 15:24:35]
  • 提交

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');
			if (re > mod) {
				re %= mod; base_cnt_mod++;
			}
		}
		base_val_mod = re;

		ll base = ans;
		while (1) {
			ans++; re = 1;
			ll try_cnt_mod=0;
			ll try_val_mod=0;
			for (int i = 1; i <= ans; i++) {
				re = re * 6;
				if (re > mod) {
					re %= mod; base_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;
				}
			}
		}
	}
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

input:

0

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

1865

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

6

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

216

output:

4

result:

ok single line: '4'

Test #6:

score: -100
Time Limit Exceeded

input:

659048550435237232393875796171343597297252783860791224966151609834498375660891507785647188078990198766575546966667938541517709208360385263203130845215396367798902376853652489767206051858708602045962531467486884777174160264291462611744982439094276291073422016146183934443085743192727084631329374278797...

output:


result: