subject
Title Description
There is one
O
U
Y
E
\sf OUYE
OUYE, he rolls every day, and finally one day he rolls himself into a daze, even
a
×
b
a\times b
a × b never mind!
But after all, he was the king of volumes and decided to write a multiplier. He is not ready to use the C + + he is good at, but uses the involuter language developed by himself. This is a programming language for inner volume, and its basic unit is inner volume. Any object o b j e c t \rm object object has two inherent attributes: volume value and volume limit.
The language supports the following operations:
- Create a new object whose volume limit is the given value and whose volume value is zero.
- Create a new object whose volume is limited to the current volume value of another object and whose volume value is zero.
- Sets the volume value of an object to zero.
- Sets the volume value of an object to its volume limit.
The only binary function in the program i n v o l u t e \rm involute The effect of involve is:
- If a a The volume value of a reaches the volume limit, or b b If the volume value of b is zero, the function ends normally. Otherwise, a a The volume value of a is increased by one, b b The volume value of b decreases by one and returns to the beginning of the function (that is, the function is called recursively).
- (developer comments for this line) a a a crazy roll until b b b is driven crazy or a a a stop when you can't roll any more! ha-ha!
In fact, in order to read data, there is a special function: create a new object whose volume limit and volume value are keyboard typed values (the same value). But you should do all the reading at the beginning of the program - we'll read it here a , b a,b a. B represents a multiplier - so it can be omitted.
For life safety, the volume limit cannot be exceeded 1 0 9 10^9 109 . Now we're going to implement it in this language a × b a\times b a × b. Store the result as the volume value of an object. Because the volume limit does not exceed 1 0 9 10^9 109. Obviously, the volume value will not exceed the volume limit, then a × b > 1 0 9 a\times b>10^9 a × b> 109 can't you figure it out? Not very good. So we still ask a × b m o d 262144 a\times b\bmod 262144 a × The value of bmod262144 is good.
Of course, the program is too long O U Y E \sf OUYE OUYE will be angry. Please control the number of statements in the program 1 0 4 10^4 Within 104. Please don't learn curly dog.
Data range and tips
a
,
b
⩽
1
0
5
a,b\leqslant 10^5
a,b⩽105 .
thinking
The worst problem with this language is that there are no logical statements!
But in fact, binary functions i n v o l u t e \rm involute Invoute gives a breakthrough. Its essence is calculation min ( a , b ) \min(a,b) min(a,b) . Yes min ( a , b ) \min(a,b) min(a,b) can obtain the partial order relationship. Note that this is a process oriented language and the results are obtained [ a > b ] [a>b] [a > b] can only be stored as volume values.
For convenience, binary function i n v o l u t e \rm involute involute is called "pour" for short, because the volume limit is the capacity and the volume value is the actual value.
Specifically, the first volume is limited to b b b, and then a a a pour b b b, next a a The remaining part of a has a pouring capacity of 1 1 1. At this time, the capacity is 1 1 The volume limit of the object of 1 is [ a > b ] [a>b] [a > b]. Using replication, we can easily create several times the volume value of any object. This lays the foundation for all operations.
For example, the simplest implementation of multiplier is to let a a a always minus min ( a , 1 ) \min(a,1) min(a,1), let c c c keep adding b ⋅ min ( a , 1 ) b\cdot\min(a,1) b⋅min(a,1) . Pay attention here b ⋅ min ( a , 1 ) b\cdot\min(a,1) The implementation method of b ⋅ min(a,1) is to create V ⋅ min ( a , 1 ) V\cdot \min(a,1) V ⋅ min(a,1) roll limit, where V V V is large enough and then b b b pour it in.
How to optimize? Don't just subtract min ( a , 1 ) \min(a,1) min(a,1) is good! Consider subtracting 2 k 2^k 2k, mandatory a ⩾ 2 k a\geqslant 2^k a ⩾ 2k. As mentioned earlier a > 2 k − 1 a>2^k-1 a> 2K − 1 can be judged and created V ⋅ [ a ⩾ 2 k ] V\cdot[a\geqslant 2^k] V ⋅ [a ⩾ 2k] roll limit, and then b ⋅ 2 k b\cdot 2^k b ⋅ 2k just pour it in.
One more thing, take the mold. and [ a ⩾ m ] [a\geqslant m] [a ⩾ m] it can be judged directly a − [ a ⩾ m ] ⋅ m a-[a\geqslant m]\cdot m A − [a ⩾ M] ⋅ m no!
The general idea is over. Then there are some details, such as b ⋅ 2 k b\cdot 2^k b ⋅ 2k may exceed 1 0 9 10^9 109. In the process of mold taking, only subtraction needs to be considered m m m once.
Calculate the number of operations. a a a yes log a \log a loga judgment a ⩾ 2 k a\geqslant 2^k a ⩾ 2k, expand this value to V ⩾ b V\geqslant b V ⩾ b times required log V ⩾ log b \log V\geqslant \log b logV ⩾ logb, so the complexity is O ( log a log b ) \mathcal O(\log a\log b) O(logalogb).
The actual test found that only 3506 3506 Line 3506.
code
Output interpretation: C is to create a new object (volume limit custom), M is to copy the object (volume limit of the new object is the volume value of the specified object), F is to fill, E is to empty, T is to pour, I is to input and P is to output.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
int a = 0, c = getchar(), f = 1;
for(; '0'>c||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(int x){
if(x > 9) writeint(x/10);
putchar((x-x/10*10)^48);
}
const int LOGB = 18;
const int CAN = 3; ///< an object with capacity +infty
const int MOD = 4; ///< an object with capacity 262143
const int ONE = 6; ///< an object with capacity 1
int tot; ///< count of all the objects
/**
* @brief create capacity b*2^k without module
* @param b an object whose @b VALUE is the multiplier
* @warning before and after this operation, @a CAN should be empty
* @warning @p b will be cleared
*/
int create(int b,int k=LOGB){
printf("M %d\n",b); int lst = ++ tot;
printf("T %d %d\n",b,CAN); ///< clear @p b
for(int i=0; i<k; ++i){
printf("F %d\nT %d %d\n",lst,lst,CAN);
printf("M %d\n",CAN); lst = ++ tot;
}
printf("E %d\n",CAN); return lst;
}
/**
* @brief if value of object @p x >= 1 + capacity of @a MOD , decrease
* @note will clear @a MOD and create log V objects
* @warning before and after this, @a ONE should be empty
**/
void modInt(int x){
printf("E %d\n",MOD); // be careful
printf("T %d %d\nT %d %d\n",x,MOD,x,ONE);
const int BIG = create(ONE,LOGB+1);
printf("T %d %d\nT %d %d\n",MOD,BIG,MOD,x);
}
const int CAN2 = 7; ///< avoid conflict
/**
* @brief create capacity b*2^k with module, stored in @p b_pow
* @param b an object, who is initially full
* @warning before and after this, @a CAN2 should be empty
* @warning @p b is taken as @p b_pow[0] therefore it's cleared
* @return the object of biggest capacity
* @note the created object is initially empty
*/
int create(int b,int b_pow[],int k=LOGB-1){
b_pow[0] = b; printf("T %d %d\n",b,CAN2);
for(int i=0; i<k; ++i){
printf("F %d\nT %d %d\n",b_pow[i],b_pow[i],CAN2);
modInt(CAN2); // maybe explode!
printf("M %d\n",CAN2);
b_pow[i+1] = ++ tot; // copy
}
printf("E %d\n",CAN2); return b_pow[k];
}
const int A = 1, B = 2;
const int RES = 5;
int b_pow[LOGB];
int main(){
puts("I"), puts("I"); // read
puts("C 1000000000"); /// @a CAN = 3
puts("C 262143"); /// @a MOD = 4
puts("C 1000000000"); /// @a RES = 5
puts("C 1"); /// @a ONE = 6
puts("C 1000000000"); /// @a CAN2 = 7
tot = 7; // keep track of count
create(B,b_pow); // pre-compute
for(int i=LOGB-1; ~i; --i){
printf("C %d\n",(1<<i)-1);
const int NOW = ++ tot;
printf("T %d %d\n",A,NOW);
printf("T %d %d\n",A,ONE);
const int BIG = create(ONE);
printf("F %d\n",b_pow[i]); ///< initially empty
printf("T %d %d\nT %d %d\n",b_pow[i],BIG,BIG,RES);
/// if @a ONE is 0, restore @a A
printf("T %d %d\nT %d %d\n",NOW,BIG,NOW,A);
modInt(RES); // maybe explode
}
printf("P %d\n",RES); // report answer
return 0;
}