HDU3292 No more tricks, Mr Nanguo滥竽充数特殊不定方程 + 矩阵应用

好题目！过的人比较少，不过咱还是过了，所以没关系，题目的综合力很好，题目讲的是南郭先生的故事，

题意：

国王喜欢听演奏，他喜欢的一个正方形每行X个人来演奏，后来他挂了，他儿子喜欢把原来的正方形拆成若干个小正方形，南郭很害怕，所以跑路了，他跑了以后，新的国王发现剩下的人刚好可以分成每组Y^2个人的 N组

总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

所以我们可以得到一个方程X^2 - 1 == N * Y^2,那么其实就是求解方程X^2 - N * Y^2 ==1,

如果n是完全平方数的话肯定是无解的，

有解的话就用矩阵来暴力求解

矩阵给出

求出方程第K大的解就可以了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; const int MOD = 8191; const int M = 2; typedef struct Matrix { int m[4][4]; }; Matrix per,d; int x,y,n,k; void init() { y = 1; while(true) { x = (ll)sqrt(n * y * y * 1.00 + 1.00); if(x * x - n * y * y == 1)break; y++; } } void clear() { for(int i=0;i
                    
                     >= 1; p = multi(p,p); } return ans; } int main() { while(scanf("%d %d",&n,&k) == 2) { int tmp = (int)sqrt(n*1.00); if(tmp * tmp == n) { puts("No answers can meet such conditions"); continue; } init(); clear(); k--; d = quick(); int ans = (d.m[0][0]*x%MOD + d.m[0][1]*y%MOD + MOD)%MOD; printf("%d\n",ans); } return EXIT_SUCCESS; }

HDU3292 No more tricks, Mr Nanguo滥竽充数 特殊不定方程 + 矩阵应用