Блог пользователя dreamoon_love_AA

Автор dreamoon_love_AA, история, 5 лет назад, По-английски

After Educational Codeforces Round 79, I want to share a problem I create this year.

It's host on 2019 Multi-University Training Contest 5.

Problem link is here.

The statement of problem is following:

Many problems require printing the probability of something. Moreover, it is common that if the answer is $$$\frac{a}{b}$$$, you should output $$$a \times b^{-1} \pmod{p}$$$ ($$$p$$$ is a prime number). In these problems, you cannot know the exact value of the probability. It's so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value x. We do so by guessing the probability is the one with the minimum $$$b$$$ such that $$$a \times b^{-1} = x \pmod{p}$$$. Now we invite you to solve this problem with us!

What the statement mentioning is quite match the situation in contest of today!

The following is the reference solution (you can use the code to get the correct fraction format output in today contest):

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef long long LL;
typedef pair<LL,LL> PLL;
const int SIZE = 1e6+10;
PLL solveWA(LL x0, LL p){
    PLL r; 
    r.S = p / x0 + 1;
    r.F = r.S * x0 - p;
    PLL x = {x0, 1LL};
    while(r.F >= r.S) {
        if(r.F * 2 < x.F) {
            PLL nxt_r = make_pair((x.F / r.F + 1) * r.F - x.F , (x.F / r.F + 1) * r.S - x.S);
            x = r;
            r = nxt_r;
        }
        else {
            LL dif = x.F - r.F;
            LL tt = x.F / dif;
            // x.F - i * dif < r.S * i - x.S * (i-1)
            // x.F - x.S < (r.S + dif - x.S) * i
            LL need = (x.F - x.S) / (r.S + dif - x.S) + 1;
            if(need <= tt) return {x.F - need * dif, (r.S - x.S) * need + x.S};
            PLL nxt_r = {x.F - tt * dif, (r.S - x.S) * tt + x.S};
            x = r;
            r = nxt_r;
        }
    }
    return r;
}
PLL solveAC(LL x0, LL p){
    PLL r; 
    r.S = p / x0 + 1;
    r.F = r.S * x0 - p;
    PLL x = {x0, 1LL};
    while(r.F >= r.S) {
        if(r.F * 2 < x.F) {
            PLL nxt_r = make_pair((x.F / r.F + 1) * r.F - x.F , (x.F / r.F + 1) * r.S - x.S);
            x = r;
            r = nxt_r;
        }
        else {
            LL dif = x.F - r.F;
            LL tt = x.F / dif;
            // x.F - i * dif < r.S * i - x.S * (i-1)
            // x.F - x.S < (r.S + dif - x.S) * i
            LL need = (x.F - x.S) / (r.S + dif - x.S) + 1;
            if(need <= tt) return {x.F - need * dif, (r.S - x.S) * need + x.S};
            PLL nxt_r = {x.F - tt * dif, (r.S - x.S) * tt + x.S};
            x = {x.F - (tt - 1) * dif, (r.S - x.S) * (tt - 1) + x.S};
            r = nxt_r;
        }
    }
    return r;
}
LL modmul(LL A,LL B,LL mod)
{
    return (A*B-(LL)((long double)A*B/mod)*mod+mod)%mod;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--) {
        LL p, x;
        scanf("%lld%lld", &p, &x);
        PLL ret=solveAC(x,p);
        printf("%lld/%lld\n",ret.F,ret.S);
    }
    return 0;
}
  • Проголосовать: нравится
  • +88
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Well, brute force is enough for the sake of seeing what my program got for a sample test.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeh... You are right. So the title is just set as some kind of content farm to cheat people to see the article XD.

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Can you explain the solution? dreamoon_love_AA

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    We have the fact $$$\frac{a}{b} \equiv x \pmod{p}$$$.

    Now introduce a new variable $$$y$$$ such that $$$a = bx - py$$$. Then we can list following inequation according to problem statement:

    $$$0 < a = bx - py < b$$$

    It can give following derivation:

    $$$0 < bx - py \Rightarrow \frac{p}{x} < \frac{b}{y}$$$ and

    $$$bx - py < b \Rightarrow \frac{b}{y} < \frac{p}{x-1}$$$.

    the value of $$$\frac{p}{x}$$$ and $$$\frac{p}{x-1}$$$ can known from input.

    Now we just want to find the smallest value of $$$b$$$ such that $$$\frac{p}{x} < \frac{b}{y} < \frac{p}{x-1}$$$.

    This is a classic problem such as 2019 Google Code Jam Round 2 — New Elements: Part 2.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Ah, 300iq just sent me the link here. It happened so that I independently developed mostly same problem which went to Petrozavodsk contest and I wrote an article about it too. Whoops. There are minor differences though like I minimize $$$\max(a,b)$$$ instead of minimizing $$$b$$$ for $$$a<b$$$, but they seem inter-reducible.