Lecture 14 of the Blue Bridge Cup -- number theory [exercises]

Preface

Blue Bridge Cup Official Website ： The Blue Bridge Cup —— College students all over the country TMT Industry events
This blog explains Blue Bridge Cup C/C++ The algorithm knowledge involved in preparing for the competition , This blog is the fourteenth lecture ： number theory 【 exercises 】

The exercises included in this blog are ：
The largest proportion
C loop
Regular problem

number theory 【 Example 】 See blog ： Blue Bridge Cup lesson 14 – number theory 【 Example 】

The content of the blog is replaced by topics , By explaining the method of the topic to help readers quickly understand the content of the algorithm , We need to pay attention to ： Learning algorithms can't just go through the brain , More practice , Please be sure to type and write the relevant code of this blog by yourself ！！！

---

The largest proportion

source ： The 7th provincial Blue Bridge Cup C++A/B Group

Subject requirements

Title Description ：

$X$ A grand prix on the planet has $M$ Level award .

The bonus for each level is a positive integer .

also , The ratio between two adjacent levels is a fixed value .

in other words ： The number of bonuses at all levels forms an equal ratio series .

such as ：$16,24,36,54$, Its ratio is equal to ：$\frac{3}{2}$.

Now? , We ran a random survey of the number of Prize Winners .

Based on this, you can calculate the maximum possible equal ratio .

Input format ：

The first line is numbers $N$ , Indicates that the next line contains $N$ A positive integer .

The second line $N$ A positive integer $X_i$, Separate with spaces , Each integer represents the amount of a person's bonus investigated .

Output format ：

One looks like $A/B$ The scores of , requirement $A$、$B$ Coprime , Represents the maximum possible scale factor .

Data range ：

$0<N<100$
$0<X_i<10^{12}$
Data guarantee there must be solutions .

sample input 1：

3
1250 200 32

sample output 1：

25/4

sample input 2：

4
3125 32 32 200

sample output 2：

5/2

sample input 3：

3
549755813888 524288 2

sample output 3：

4/1

Thought analysis

Suppose the original sequence is $a,a\ast (p/q{)}^1,a\ast (p/q{)}^2,...,a\ast (p/q{)}^{(}n-1)$
Suppose the extracted sequence $b0,b1,...,b(N-1)$ ( From small to large, the order is arranged )
$b1/b0,b2/b0,...,b(N-1)/b0-->(p/q{)}^{x}1,(p/q{)}^{x}2,...,(p/q{)}^x(N-1)$
So what we want is ：$(p/q{)}^k(p/q)>1$, So make $k$ Maximum , The o $(p/q{)}^{x}1$~$(p/q{)}^x(N-1)$ Maximum common divisor of , In fact, it is to ask for $x1$~$x(N-1)$ Maximum common divisor of
Here we use more phase subtraction , Because we didn't get the exact $x1$~$x(N-1)$ How much is the , We only have $(p/q{)}^{x}1,(p/q{)}^{x}2,...,(p/q{)}^x(N-1)$ Values of these

More subtraction ： First step ： Any given two positive integers ; Determine whether they are all even numbers . if , Then use $2$ reduction ; If not, proceed to step 2 .
The second step ： Subtract the smaller number from the larger number , Then compare the difference with the smaller number , And subtract decimals from large numbers . Continue this operation , Until the resulting subtraction and difference are equal .
Then some of the missing in the first step $2$ The product of and the number in the second step is the greatest common divisor .

More phase subtraction always subtracts the smaller from the larger

What we're going to use here is the index , So let $(p/q{)}^{x}1,(p/q{)}^{x}2,...,(p/q{)}^x(N-1)$, Two for two , Mutual division , Except that the result is $1$, namely x1=x2, At this time, the power is $0$, The result is $1$, Calculate the numerator and denominator separately , The result is the same because , The power of numerator and denominator is the same

Code

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 110;

int n;
LL a[N], b[N], x[N];

LL gcd(LL a, LL b)
{
    
    return b ? gcd(b, a % b) : a;
}

LL gcd_sub(LL a, LL b)
{
    
    if (a < b) swap(a, b);
    if (b == 1) return a;
    return gcd_sub(b, a / b);
}

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> x[i];

    sort(x, x + n);
    int cnt = 0;
    for (int i = 1; i < n; i ++ )
        if (x[i] != x[i - 1])
        {
    
            LL d = gcd(x[i], x[0]);
            a[cnt] = x[i] / d;
            b[cnt] = x[0] / d;
            cnt ++ ;
        }

    LL up = a[0], down = b[0];
    for (int i = 1; i < cnt; i ++ )
    {
    
        up = gcd_sub(up, a[i]);
        down = gcd_sub(down, b[i]);
    }

    cout << up << '/' << down << endl;

    return 0;
}

C loop

Subject requirements

Title Description ：

about C The loop of language , Form like ：

for (variable = A; variable != B; variable += C)
  statement;

Excuse me at $k$ The loop will end several times in a bit storage system .

If it ends within a finite number of times , Then the number of cycles is output . Otherwise, the output loop is dead .

Input format ：

Multiple sets of data , Each set of data has four integers in a row $A,B,C,k$.

Read in to $0$$0$$0$$0$ end .

Output format ：

If it ends within a finite number of times , Then the number of cycles is output .

Otherwise output $FOREVER$.

Data range ：

$1\le k\le 32,$
$0\le A,B,C<2^k$

sample input ：

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

sample output ：

0
2
32766
FOREVER

Thought analysis

This question uses extended euclidean algorithm , See the blog for specific principles ： Math knowledge ： extended euclidean algorithm

Pay attention to this question yes $k$ Bit storage system So there is a loop plus a loop and then it is equal For example $16$ Bit system In limine $a=3c=1b$ Every time add $2$ Finally, the conditions can be reached
$a$ Can achieve $k$ Bit operating system
So we can get
$(a+xc)$
Equivalent to
$a+xc-y{2}^k=b$
Equivalent to
$xc-y\ast 2^k=b-a$
Only $xy$ Two unknowns So the extended Euclidean algorithm
Find out $gcd(a,b)$
In this case, if the greatest common divisor is not $b-a$ Multiple Then there is no solution
Then multiply both sides at the same time $(b-a)/gcd(a,b)$
Review the bezu equation
$ax+by=gcd(a,b)$
there $b$ Namely $1<<k$
Therefore, we can draw a conclusion from the above
$xmin=x$( This $x$ Is multiplied by a multiple $x$) %(b/gcd(a,b))

Code

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    
    if (b == 0)
    {
    
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    
    LL a, b, c, k;

    while (cin >> a >> b >> c >> k, a || b || c || k)
    {
    
        LL x, y;
        LL z = 1ll << k;
        LL d = exgcd(c, z, x, y);
        if ((b - a) % d) cout << "FOREVER" << endl;
        else
        {
    
            x *= (b - a) / d;
            z /= d;
            cout << (x % z + z) % z << endl;
        }
    }

    return 0;
}

Regular problem

source ： The 8th provincial Blue Bridge Cup C++A Group , The 8th provincial Blue Bridge Cup JAVAA Group

Subject requirements

Title Description ：

Consider a simple regular expression ：

Only by $x$$($$)$$|$ Regular expressions composed of .

Xiao Ming wants to find the length of the longest string that this regular expression can accept .

for example $((xx|xxx)x|(x|xx))xx$ The longest string that can be accepted is ： $xxxxxx$, The length is $6$.

Input format ：

One by $x()|$ Regular expressions composed of .

Output format ：

Output the length of the longest string that the given regular expression can accept .

Data range ：

Input length is not more than $100$, To guarantee legality .

sample input ：

((xx|xxx)x|(x|xx))xx 

sample output ：

6

Thought analysis

This picture is from ：https://www.acwing.com/user/myspace/index/1099/

Code

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int k;
string str;

int dfs()
{
    
    int res = 0;
    while (k < str.size())
    {
    
        if (str[k] == '(')  //  Handle  (......)
        {
    
            k ++ ;  //  skip  '('
            res += dfs();
            k ++ ; //  skip  ')'
        }
        else if (str[k] == '|')
        {
    
            k ++ ;  //  skip  '|'
            res = max(res, dfs());
        }
        else if (str[k] == ')') break;
        else
        {
    
            k ++ ;  //  skip  'x'
            res ++ ;
        }
    }

    return res;
}

int main()
{
    
    cin >> str;
    cout << dfs() << endl;

    return 0;
}

---