Best Solver

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)

Total Submission(s): 1115 Accepted Submission(s): 645

Problem Description

The so-called best problem solver can easily solve this problem, with his/her childhood sweetheart.

It is known that

Input

An integer

Output

The output contains exactly

Sample Input

7 0 46337 1 46337 3 46337 1 46337 21 46337 321 46337 4321 46337

Sample Output

Case #1: 97 Case #2: 969 Case #3: 16537 Case #4: 969 Case #5: 40453 Case #6: 10211 Case #7: 17947

Source

Recommend

wange2014

题目描述：

　　对于，给出x和mod，求y向下取整后取余mod的值为多少？

分析：

　　这种(a+sqrt(b))^n%mod，向下取整取余的式子有个递推式 S(n) = 2*a*S(n-1)+(b-a*a)*S(n-2) 这个式子得到的结果是向上取整，我们这里是向下取整，所以最后得到的结果还要减一

　　我这篇博客https://www.cnblogs.com/l609929321/p/9398349.html有这个递推式的推导过程

　　由上诉递推式不难得到：S(n) = (10*S(n-1)-S(n-2)+mod)%mod

　　但是这个题目的指数1+2^x(x<2^32)非常大，就算用矩阵快速幂也不行，所以我们得对式子进行一次优化

　　看到指数很大的类似斐波拉数列问题（都是线性递推式）很容易的想到找循环节

　　因为mod<=46337，所以我们直接遍历求前面46337项一定会出现循环节，然后记录下循环节的位置就好　　

　　（以后找模一个数的周期最大取到他的三倍，证明博客：https://www.xuebuyuan.com/1198038.html）

　　再对指数按照循环节的位置进行取模就可以了

AC代码

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e5 + 10;const ll mod = 1e9 + 7;ll r[maxn], ans[maxn], x, m;ll qow( ll b, ll n, ll mod ) { ll ans = 1; while( n ) { if( n&1 ) { ans = ans*b%mod; } b = b*b%mod; n /= 2; } return ans;}int main() { ll T, t = 0; cin >> T; while( T -- ) { ll x, m; t ++; cin >> x >> m; ans[0] = 2, ans[1] = 10; for( ll i = 2; i < maxn; i ++ ) { ans[i] = (10*ans[i-1]-ans[i-2]+m)%m; //根据类似斐波拉数得到的一个递推式 if( ans[i-1] == ans[0] && ans[i] == ans[1] ) { //因为x很大，这里计算了循环周期 r[m] = i-1; break; } } ll k = (1+qow(2,x,r[m]))%r[m]; cout << "Case #" << t << ": " << (ans[k]-1+m)%m << endl; } return 0 ;}