chcrt0x的博客

2024-03-08 20:52:59 By chcrt0x

首先，我们需要理解题目中定义的函数f(t)。这个函数的作用是将字符串t映射成一个整数值。具体地，对于一个长度为n的字符串t，我们将其每个字符转换成对应的数字（a=0, b=1, ..., z=25），然后根据26的幂次方加权求和，并取模p。

我们知道时光机会对输入的密码旋转0到n-1次，得到n个字符串。对于每个字符串，我们可以通过f函数计算出一个对应的整数值。

题目给出了n个值h0, h1, ..., hn-1，表示时光机存储的n个值。我们需要找到一个密码s，使得对于任意0≤k<n，f(ak) = hk。

算法的关键在于求解密码s。我们可以通过反向推导，根据已知的h0, h1, ..., hn-1，以及MOD的值，来求解密码s。

在代码中，我们先通过快速幂算法计算出inv，然后根据inv的值分情况讨论：

如果inv不为0，我们可以根据公式1ll * (26ll * h[i] % MOD + MOD - h[i + 1]) % MOD * inv % MOD + 97来求解密码s。

如果inv为0，我们需要将h0, h1, ..., hn-1转换成对应的字母，然后输出即可。

 C++ 20
#import "bits/stdc++.h"
#define endl '\n'
#define ll long long

using namespace std;

const int MAX = 100100; 
int n, MOD, h[MAX], a[MAX];

int fpow(int a, int b)
{
    int s = 1;
    while(b) {
        if(b & 1)
        { s = 1ll * s * a % MOD; }
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return s;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> MOD;
    int inv = fpow(fpow(26, n) - 1, MOD - 2);
    for(int i = 0; i < n; ++i) { cin >> h[i]; }
    h[n] = h[0];
    if(inv) {
        for(int i = 0; i < n; ++i) 
        { cout << char(1ll * (26ll * h[i] % MOD + MOD - h[i + 1]) % MOD * inv % MOD + 97); }
    }
    else {
        for(int i = n - 1; ~i; --i) { a[i] = h[0] % 26, h[0] /= 26; }
        for(int i = 0; i < n; ++i) { cout << char(a[i] + 97); }
    }
    cout << endl;
    return 0;
}

阅读全文

UOJ 48 题解

2024-03-08 20:32:28 By chcrt0x

假设我们有两个原子，它们的核聚变特征值分别为 x 和 y。

首先，我们找出 x 的所有质因数。这可以通过试除法来实现。我们从 2 开始尝试将 x 进行分解，如果 x 能被 i 整除，则说明 i 是 x 的一个质因数。我们重复这个过程，直到 x 无法再被整除为止。

对于第二个原子的核聚变特征值 y，我们计算 x 和 y 的最大公约数 d = gcd(x, y)。最大公约数可以通过欧几里得算法来计算。

如果 d 等于 1，则说明 x 和 y 互质，即它们没有共同的质因数，无法进行核聚变反应，输出 -1。

如果 d 大于 1，说明 x 和 y 存在一个共同的质因数，即它们可以进行核聚变反应。我们需要找到这个共同的质因数中最大的一个，即次大公约数。这个次大公约数即为 x 的所有质因数中与 d 同时也是质因数的最大值。

最后，输出这个次大公约数作为核聚变反应的强度。

 C++ 20
#import "bits/stdc++.h"
#define endl '\n'
#define ll long long

using namespace std;

const int maxn = 200001;
const int mod = 10007;
const int inf = 0x3f3f3f3f;

ll a[maxn], p[maxn];
int n, Num;
char CH[12];

inline void P(int x)
{
    Num = 0;
    if(!x) {
        cout << 0 << endl;
        return;
    }
    while(x > 0) { CH[++Num] = x % 10, x /= 10; }
    while(Num) { putchar(CH[Num--] + 48); }
    cout << endl;
    return ; 
}

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    { scanf("%lld", &a[i]); }
    ll tot = 0;
    ll x = a[0];
    for(ll i = 2; i <= sqrt(x); i ++) {
        if(x % i == 0) {
            while(x % i == 0) { x /= i; }
            p[tot++] = i;
        }
    }
    for(int i = 0; i < n; i ++) {
        ll d = gcd(a[0], a[i]);
        int flag = 1;
        for(int j = 0; j < tot; j ++) {
            if(d % p[j] == 0) {
                printf("%lld ", d / p[j]);
                flag = 0;
                break;
            }
        }
        if(flag) {
            if(d != 1)
            { cout << 1 << ' '; }
            else
            { cout << -1 << ' '; }
        }
    }
    return 0;
}

阅读全文

博客

UOJ 74 题解

UOJ 48 题解