首页 > ACM题库 > HDU-杭电 > HDU 3221-Brute-force Algorithm-最小生成树-[解题报告]HOJ
2014
03-07

HDU 3221-Brute-force Algorithm-最小生成树-[解题报告]HOJ

Brute-force Algorithm

问题描述 :

Professor Brute is not good at algorithm design. Once he was asked to solve a path finding problem. He worked on it for several days and finally came up with the following algorithm:
Alice’s Cube

Any fool but Brute knows that the function “funny” will be called too many times. Brute wants to investigate the number of times the function will be called, but he is too lazy to do it.

Now your task is to calculate how many times the function “funny” will be called, for the given a, b and n. Because the answer may be too large, you should output the answer module by P.

输入:

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases.

For each test cases, there are four integers a, b, P and n in a single line.
You can assume that 1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000.

输出:

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases.

For each test cases, there are four integers a, b, P and n in a single line.
You can assume that 1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000.

样例输入:

3
3 4 10 3
4 5 13 5
3 2 19 100

样例输出:

Case #1: 2
Case #2: 11
Case #3: 12

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3221

矩阵乘法和数学的结合。

由题目意思可知:f[n]=f[n-1]*f[n-2];

f的前面几项可以罗列出来:

a^1*b^0,a^0*b^1,a^1*b^1,a^1*b^2,a^2*b^3….

可以发现a的指数和b的指数均类似于斐波那契数列。

用矩阵的快速幂可以很快的求出第n项a和b的指数分别是多少。

但是这个指数会非常大,存不下来,需要对一个数去模。

这里需要用到一个公式:

A^B%C=A^( B%Phi[C] + Phi[C] )%C   (B>=Phi[C])

Phi[C]表示不大于C的数中与C互质的数的个数,可以用欧拉函数来求:

找到C的所有素因子。

Phi[C]=C*(1-1/q1)*(1-1/q2)*(1-1/q3)*….*(1-1-qk);

q1,q2,q3…qk表示C的素因子。

到这里基本上就能解决了。

code:

# include<stdio.h>
 # include<string.h>
 # include<stdlib.h>
 # define N 1000005
 int visit[N],prime[N],K;
 __int64 P,Phi;
 struct matrix{
     __int64 A[2][2];
 };
 void intt()
 {
     int i,j;
     memset(visit,0,sizeof(visit));
     for(i=2;i<=1000;i++)
     {
         if(visit[i]==0)
         {
             for(j=i+i;j<=1000000;j+=i)
             {
                 visit[j]=1;
             }
         }
     }
     K=0;
     for(j=2;j<=1000000;j++)
         if(visit[j]==0) prime[++K]=j;
 }
 matrix power(matrix ans1,matrix ans2)
 {
     int i,j,k;
     matrix ans;
     for(i=0;i<=1;i++)
     {
         for(j=0;j<=1;j++)
         {
             ans.A[i][j]=0;
             for(k=0;k<=1;k++)
             {
                 ans.A[i][j]+=ans1.A[i][k]*ans2.A[k][j];
                 if(ans.A[i][j]>Phi)
                 {
                     ans.A[i][j]=ans.A[i][j]%Phi+Phi;
                 }
             }
         }
     }
     return ans;
 }
 matrix mod(matrix un,__int64 k)
 {
     matrix ans;
     ans.A[0][0]=1;
     ans.A[0][1]=0;
     ans.A[1][0]=0;
     ans.A[1][1]=1;
     while(k)
     {
         if(k%2) ans=power(ans,un);
         un=power(un,un);
         k/=2;
     }
     return ans;
 }
 __int64 mod1(__int64 a,__int64 k)
 {
     __int64 ans;
     ans=1;
     while(k)
     {
         if(k%2) 
         {
             ans=ans*a;
             ans%=P;
         }
         a=a*a;
         a%=P;
         k/=2;
     }
     return ans%P;
 }
 int main()
 {
     int i,ncase,t;
     __int64 a,b,aa,bb,n,num,num1,num2;
     //freopen("3221.in","r",stdin);
     //freopen("32211.out","w",stdout);
     matrix init,ans;
     intt();
     scanf("%d",&ncase);
     for(t=1;t<=ncase;t++)
     {
         scanf("%I64d%I64d%I64d%I64d",&a,&b,&P,&n);
         printf("Case #%d: ",t);
         if(n==1) {printf("%I64d\n",a%P);continue;}
         else if(n==2) {printf("%I64d\n",b%P); continue;}
         else if(n==3) {printf("%I64d\n",a*b%P);continue;}
         if(P==1) {printf("0\n");continue;}
         init.A[0][0]=0;
         init.A[0][1]=1;
         init.A[1][0]=1;
         init.A[1][1]=1;
         //  A^B % C = A ^ ( B % phi[C] + phi[C] ) %C  ( B >= phi[C] ) ,phi[C]表示与C互质的数的个数
         Phi=1;
         num=P;
         for(i=1;i<=K;i++)
         {
             if(prime[i]>P) break;
             if(P%prime[i]==0) {Phi*=(prime[i]-1);num/=prime[i];}
         }
         ///phi[C]=C*(1-1/p1)*(1-1/p2)*...*(1-1/pt);p1,p2,...pt表示C的素因子
         Phi*=num;//Phi表示phi[C]
 
 
         ans=mod(init,n-3);///求指数
 
 
         num1=ans.A[1][1];///a的指数
         num2=ans.A[0][1]+ans.A[1][1];///b的指数
         if(num2>Phi) num2=num2%Phi+Phi;
 
         aa=mod1(a,num1);///a^num1%p;
         bb=mod1(b,num2);//b^num2%p;
 
         printf("%I64d\n",aa*bb%P);
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/183zyz/archive/2012/05/11/2495401.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。