The Preliminary Contest for ICPC Asia Nanjing 2019

发布于 2019-09-21  47 次阅读


The Preliminary Contest for ICPC Asia Nanjing 2019

认真写的(ABFH)4题(缓慢更新题目中)

导航

A.The beautiful values of the palace

B.super_log

F. Greedy Sequence

H.Holy Grail

A.The beautiful values of the palace

题目

样例

输入

输出

代码

 

说明

B. super_log

这是一道简单(划掉)这不是一个简单的快速幂,需要欧拉降幂!!!!

题目

In Complexity theory, some functions are nearly O(1), but it is greater then O(1). For example, the complexity of a typical disjoint set is O(nα(n))). Here α(n) is Inverse Ackermann Function, which growth speed is very slow. So in practical application, we often assume α(n) \le 4.


However O(α(n)) is greater than O(1), that means if nn is large enough, α(n)α(n) can greater than any constant value.


Now your task is let another slowly function log*x reach a constant value b. Here log*is iterated logarithm function, it means “the number of times the logarithm function iteratively applied on x before the result is less than logarithm base a”.


Formally, consider a iterated logarithm function log_{a}^* ​  


Find the minimum positive integer argument x, let log_{a}^* (x) \ge b. The answer may be very large, so just print the result x after mod m.


Input

The first line of the input is a single integer T(T\le 300) indicating the number of test cases.
Each of the following lines contains 3 integers a , bb and mm.
1 \le a \le 1000000
0 \le b \le 1000000
1 \le m \le 1000000
Note that if a==1, we consider the minimum number x is 1.
Output

For each test case, output xx mod mm in a single line.
HintIn the 4-th query, a=3and b=2. Then log_{3}^* (27) = 1+ log_{3}^* (3) = 2 + log_{3}^* (1)=3+(-1)=2 \ge b, so the output is 27 mod 16 = 11.

样例

输入

 5
2 0 3
3 1 2
3 1 100
3 2 16
5 3 233

输出

1
1
3
11
223

代码

 

说明

不要以为这个是求log,其实是求a^{a^{...}}由于快速幂会TLE,所以要用欧拉函数降幂。

F. Greedy Sequence

题目

样例

输入

输出

代码

 

说明

H. Holy Grail

题目

As the current heir of a wizarding family with a long history, unfortunately, you find yourself forced to participate in the cruel Holy Grail War which has a reincarnation of sixty years.However,fortunately,you summoned a Caster Servant with a powerful Noble Phantasm.When your servant launch her Noble Phantasm,it will construct a magic field,which is actually a directed graph consisting of n vertices and m edges. More specifically, the graph satisfies the following restrictions :

Does not have multiple edges(for each pair of vertices x and y, there is at most one edge between this pair of vertices in the graph) and does not have self-loops(edges connecting the vertex with itself).
May have negative-weighted edges.
Does not have a negative-weighted loop.
n<=300 , m<=500.
Currently,as your servant's Master,as long as you add extra 6 edges to the graph,you will beat the other 6 masters to win the Holy Grail.

However,you are subject to the following restrictions when you add the edges to the graph:

Each time you add an edge whose cost is c,it will cost you c units of Magic Value.Therefore,you need to add an edge which has the lowest weight(it's probably that you need to add an edge which has a negative weight).
Each time you add an edge to the graph,the graph must not have negative loops,otherwise you will be engulfed by the Holy Grail you summon.

样例

输入

输出

代码

 

说明


Σσ(・Д・;)我我我什么都没做!!!