ANKTRAIN
（1）问题描述：
Rahul and Rashi are off to the wedding of a close relative. This time they have to travel without their guardians. Rahul got very interested in the arrangement of seats inside the train coach. The entire coach could be viewed as an arrangement of consecutive blocks of size 8. Berth Number Compartment 1 - 8 1 9 - 16 2 17 - 24 3 ... and so on Each of these 8-size blocks are further arranged as: 1LB, 2MB, 3UB, 4LB, 5MB, 6UB, 7SL, 8SU 9LB, 10MB, ... ... ... Here LB denotes lower berth, MB middle and UB upper berth. The following berths are called Train-Partners: 3UB | 6UB 2MB | 5MB 1LB | 4LB 7SL | 8SU and the pattern is repeated for every set of 8 berths. Rahul and Rashi are playing this game of finding the train partner of each berth. Can you write a program to do the same? Input: The first line of input contains a single integer T, denoting the number of test cases to follow. Each of the next T lines contain a single integer N, the berth number whose neighbor is to be found out. Output: The output should contain exactly T lines each containing the berth of the neighbor of the corresponding seat. Constraints: Subtasks Subtask #1 (50 points): 1 ≤ T ≤ 8 1 ≤ N ≤ 8 Subtask #2 (50 points): 1 ≤ T ≤ 100 1 ≤ N ≤ 500 Example: Example Input: 3 1 5 3 Output: 4LB 2MB 6UB（2）要点：水题
（3）代码：
#include <stdio.h> #include <string> using std::string; int main() { static const unsigned int module = 8; static string sans[module] = { "SL","LB","MB","UB","LB","MB","UB","SU" }; static int ians[module] = { -1,+3,+3,+3,-3,-3,-3,+1 }; unsigned int nCases = 0;scanf("%d",&nCases); for(unsigned int iCases = 1;iCases <= nCases;++iCases) { unsigned int n = 0;scanf("%d",&n); unsigned int r = n%module; printf("%d%s\n",n+ians[r],sans[r].c_str()); } return 0; }
KIRLAB
（1）问题描述：
Kirito faced dangerous labyrinth, and now he require your help. He's in tunnel, which contain N different rooms. Each room contain Ai monsters inside it. He starts from room 1. Every time he stay near room X, he may go in and clear it from monsters, or just leave room locked and move to the room X+1. However, if he clears a room with K monsters, then the next room he clears consists of L monsters, then greater common divisor of K and L must be greater than 1, otherwise he will die (awful curse). Formally, let us say that the order of rooms visited by him be i1, i2, , .. it, then gcd(Aij, Aij + 1) > 1 for all j < t. Help him cross all the rooms by clearing the maximum amount of rooms. Input The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains one integer N denoting the number elements in sequence. The second line of each test case contains N integers where i-th integer is number of monsters in room Ai. Output For each test case, output maximum amount of rooms he could clear, before crossing all the rooms (Kirito should survive). Constraints 1 ≤ T ≤ 10 1 ≤ N ≤ 10^5 1 ≤ ai ≤ 10^7 Subtasks Subtask 1: 1 ≤ N ≤ 10^3 - 30 points Subtask 2: Original constraints - 70 points Example Input: 2 7 13 2 8 6 3 1 9 6 1 2 2 3 3 1 Output: 5 2 Explanation Example 1. Kirito can clear the monster in the rooms 2, 3, 4, 5, 7 in order. These rooms consist of monsters 2 8 6 3 9, respectively. You can check that gcd(2, 8), gcd(8, 6), gcd(6, 3) and gcd(3, 9), all are greater than 1. Example 2. Kirito can clear the monster in the rooms numbered 2, 3, each of these two rooms contains two monsters. As we know that gcd(2, 2) = 2 > 1. There is one more possible solution, Kirito can clear the monsters in the rooms numbered 4, 5, these rooms contains 3 monster each, he can clear these rooms as gcd(3, 3) = 3 > 1.（2）要点：注意全1的情况
（3）代码：
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <assert.h> using std::vector; // 计算所有 <= maxn的数,factors[v]是v的一个素因子 static bool generate_factors(unsigned int maxn,vector<unsigned int>& factors) { factors.clear();factors.resize(maxn+1,1); for(unsigned int p = 2;p <= maxn;++p) { if(1 != factors[p]) continue; if(p > maxn/p) continue; for(unsigned int v = p*p;v <= maxn;v += p) factors[v] = p; } return true; } // 计算n的素分解,其中factors[v]是v的一个素因子,pfactors用于存储素因子的值,pcounts用于存储素因子的指数 static bool calc_prime_factors(unsigned int n,const vector<unsigned int>& factors,vector<unsigned int>& pfactors,vector<unsigned int>& pcounts) { vector<unsigned int> primes;primes.reserve(10); unsigned int v = n; for(;1 != factors[v];) { unsigned int p = factors[v]; primes.push_back(p); //for(;0 == (v%p);v /= p); v /= p; } if(0 == primes.size() || 1 != v) primes.push_back(v); std::sort(primes.begin(),primes.end()); assert(primes.size() > 0); pfactors.clear();pfactors.reserve(primes.size()); pfactors.push_back(primes[0]);pcounts.push_back(1); for(size_t i = 1;i < primes.size();++i) { if(primes[i] != primes[i-1]) { pfactors.push_back(primes[i]);pcounts.push_back(1); } else { ++pcounts[pcounts.size()-1]; } } return true; } int main() { static const unsigned int maxn = 10000000; vector<unsigned int> factors; generate_factors(maxn,factors); static unsigned int dps[maxn+1] = { 0 }; unsigned int nCases = 0;scanf("%d",&nCases); for(unsigned int iCases = 1;iCases <= nCases;++iCases) { memset(dps,0,sizeof(dps)); unsigned int n = 0,v = 0,ans = 1;scanf("%d",&n); for(unsigned int i = 0;i < n;++i) { scanf("%d",&v); if(1 == v) continue; vector<unsigned int> pfactors,pcounts; calc_prime_factors(v,factors,pfactors,pcounts); unsigned int maxv = 0; for(size_t i = 0;i < pfactors.size();++i) { if(dps[pfactors[i]] > maxv) maxv = dps[pfactors[i]]; } ++ maxv; for(size_t i = 0;i < pfactors.size();++i) { dps[pfactors[i]] = maxv; } if(maxv > ans) ans = maxv; //for(unsigned int i = 0;i <= 14;++i) printf("%d ",dps[i]); //printf("\n"); } printf("%u\n",ans); } return 0; }BASE
（1）问题描述：
Chef has recently learned about number bases and is becoming fascinated. Chef learned that for bases greater than ten, new digit symbols need to be introduced, and that the convention is to use the first few letters of the English alphabet. For example, in base 16, the digits are 0123456789ABCDEF. Chef thought that this is unsustainable; the English alphabet has only 26 letters, so this scheme can only work up to base 36. But this is no problem for Chef, because Chef is very creative and can just invent new digit symbols when she needs them. (Chef is very creative.) Chef also noticed that in base two, all positive integers start with the digit 1! However, this is the only base where this is true. So naturally, Chef wonders: Given some integer N, how many bases b are there such that the base-b representation of N starts with a 1? Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of one line containing a single integer N (in base ten). Output For each test case, output a single line containing the number of bases b, or INFINITY if there are an infinite number of them. Constraints Subtasks Subtask #1 (16 points): 1 ≤ T ≤ 10^3 0 ≤ N < 10^3 Subtask #2 (24 points): 1 ≤ T ≤ 10^3 0 ≤ N < 10^6 Subtask #3 (28 points): 1 ≤ T ≤ 10^3 0 ≤ N < 10^12 Subtask #4 (32 points): 1 ≤ T ≤ 10^5 0 ≤ N < 10^12 Example Input: 4 6 9 11 24 Output: 4 7 8 14（2）要点：问题实际上是求解(b,n)使得，b^n <= x < 2*b^n，可以对于0 <= n < maxb,二分查找
（3）代码：
#include <stdio.h> #include <vector> #include <string.h> #include <algorithm> #include <assert.h> #include <math.h> using std::vector; template<class data_t> static void quick_exp(const data_t& a,data_t& e,unsigned long long x) { } class FindPredMin { private: unsigned long long val; unsigned int ibit; public: FindPredMin(unsigned long long v,unsigned int x):val(v),ibit(x) { ; } public: bool operator()(const unsigned int* data,size_t size,unsigned long long p) { unsigned long long res = 1; quick_exp(p,res,ibit); unsigned long long t = val/res; if(t < 2) return true; return false; } }; class FindPredMax { private: unsigned long long val; unsigned int ibit; public: FindPredMax(unsigned long long v,unsigned int x):val(v),ibit(x) { ; } public: bool operator()(const unsigned int* data,size_t size,unsigned long long p) { unsigned long long res = 1; quick_exp(p,res,ibit); unsigned long long t = val/res; if(t >= 1) return true; return false; } }; // 找到最小的满足要求的data[k]的k template<class T,class Pred> static unsigned long long binary_find_min(const T* data,size_t size,unsigned long long lo,unsigned long long hi,Pred pred) { } // 找到最大的满足要求的data[k]的k template<class T,class Pred> static unsigned long long binary_find_max(const T* data,size_t size,unsigned long long lo,unsigned long long hi,Pred pred) { } unsigned long long slove(unsigned long long v) { static const unsigned long long maxv = 1000000000000LL; static const unsigned int maxbit = 40; // 2^maxbit >= maxv unsigned long long maxb[maxbit+1] = { 0 }; // maxb[i]^i >= maxv if(0 == maxb[maxbit]) { for(unsigned int ibit = 1;ibit <= maxbit;++ibit) { long double root = pow(1.0*maxv,1.0/ibit); maxb[ibit] = (unsigned long long)(root + 1); //unsigned long long res = 1; //quick_exp(maxb[ibit],res,ibit); //assert(res >= maxv); } } if(0 == v) return 0; if(1 == v) return (unsigned long long)(-1); // 求(b,ibit)的个数,使得1 <= v/(b^ibit) < 2,其中(b > 2) unsigned long long ans = 0; for(unsigned int ibit = 1;ibit <= maxbit;++ibit) { unsigned long long lo = 1,hi = maxb[ibit]; unsigned long long mini = binary_find_min<unsigned int,FindPredMin>(NULL,0,lo,hi,FindPredMin(v,ibit)); unsigned long long maxi = binary_find_max<unsigned int,FindPredMax>(NULL,0,lo,hi,FindPredMax(v,ibit)); //unsigned long long maxi = 0; if(mini > maxi) continue; ans += maxi - mini + 1; } return ans; } int main() { unsigned int nCases = 0;scanf("%d",&nCases); for(unsigned int iCases = 1;iCases <= nCases;++iCases) { unsigned long long n = 0;scanf("%lld",&n); unsigned long long ans = slove(n); if((unsigned long long)(-1) != ans) printf("%llu\n",ans); else printf("INFINITY\n"); } return 0; }text
（1）问题描述
（2）要点：
（3）代码：
text
（1）问题描述
（2）要点：
（3）代码：
text
（1）问题描述
（2）要点：
（3）代码：
text
（1）问题描述
（2）要点：
（3）代码：
text
（1）问题描述
（2）要点：
（3）代码：
text
（1）问题描述
（2）要点：
（3）代码：
text
（1）问题描述
（2）要点：
（3）代码：
