POJ (2262 Goldbach's Conjecture)
题目大意：给你一个大于等于6的偶数，让你求出两个奇素数，a,b 满足 x=a+b； a,b也许有多对，但是只需要求出 b-a最大的那对！
题目分析： 这题直接暴力就可以了，先求出奇素数，第一队就是满足条件的了
代码：//pku 2909 pku2262 hdu1397 AC代码都差不多
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[500020];
int flag[1000002]={0};
void init(){
int k=1;
for(int i=2;i<=1000000;i+=2)
flag[k]=1;//“0”代表是奇素数，”1“代表不是！
for(int i=3;i<=1000000;i+=2){
if(!flag[i]){
s[k++]=i;
for(int j=2*i;j<=1000000;j+=i)
flag[j]=1;
}
}
}
int main(){
init();
long n,i;
while(scanf("%ld",&n),n){
if(n%2==1)
continue;
long long p=n/2+1;
for(i=1;s[i]<=p;i++){
int k=n-s[i];
if(!flag[k]){
printf("%ld = %d + %d\n",n,s[i],k);
break;//注意第一对就是题目要的，这里要直接跳出了 不然TLE
}
}
if(i>p)
printf("Goldbach's conjecture is wrong.\n");//这里要不要无所谓 其实
}
return 0;
}
PKU (1730 Perfect Pth Powers)
题目分析： 就是给你 X 求 最大的p满足 X=a^p 特别提醒一下 X可正可负！
这里我用的是暴力，就是第一种 枚举+二分，第二种是 比较高效的暴力0MS过的！
这里唯一要考虑的是，首先 如果是正值我们不用做任何处理，如果是负数， 那么他的p肯定不能是偶数，如果是偶数，p次方后 肯定是整数，所以会与答案 有 冲突， 如果还有不懂的 请您留言
代码
#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
int i;
double n;
while(cin>>n,n){
int maxn=1;
bool flag=false;
if(n<0){
n*=-1;
flag=true;
}
for(i=32;i>=1;i--){
double up=ceil(pow(n,1.0/i));
double down=floor(pow(n,1.0/i));
if(fabs(n-pow(up,i))<1e-8||fabs(n-pow(down,i))<1e-8) {
if(flag){
if(i%2==1){
maxn=i; break;
}
}
else {
maxn=i;
break;
}
}
}
printf("%d\n",maxn);
}
return 0;
}
#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
long long n,i,t,maxn;
while(cin>>n,n){
maxn=0;
bool flag=false;
if(n<0){
n*=-1;
flag=true;
}
long long k=(long long)sqrt(n);
for(i=2;i<=k;i++){
long long m=n;
t=0;
while(m%i==0){
t++;
m/=i;
}
if(m==1){
if(flag){
if(t%2==1)
maxn=maxn>t? maxn:t;
else
continue;
}
else
maxn=maxn>t? maxn:t;
}
}
if(maxn==0)
maxn=1;
printf("%lld\n",maxn);
}
return 0;
}
PKU( 2191 Mersenne Composite Numbers )
题目大意：
#include<stdio.h>
int main()
{
int n,i;
int b[10]={11,23,29,37,41,43,47,53,59};
char a1[10][100] ={"23 * 89 = 2047 = ( 2 ^ 11 ) - 1",
"47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1",
"233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1",
"223 * 616318177 = 137438953471 = ( 2 ^ 37 ) - 1",
"13367 * 164511353 = 2199023255551 = ( 2 ^ 41 ) - 1",
"431 * 9719 * 2099863 = 8796093022207 = ( 2 ^ 43 ) - 1",
"2351 * 4513 * 13264529 = 140737488355327 = ( 2 ^ 47 ) - 1",
"6361 * 69431 * 20394401 = 9007199254740991 = ( 2 ^ 53 ) - 1",
"179951 * 3203431780337 = 576460752303423487 = ( 2 ^ 59 ) - 1"};
scanf("%d",&n);
for(i=0;i<9;i++)
{
if(n>b[i])
printf("%s\n",a1[i]);
else break;
}
return 0;
}
POJ （2739 Sum of Consecutive Prime Numbers）
题目分析：直接枚举就可以了 二重循环！
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[10000],k;
bool flag[10001];
int get_pri(){
int i;
memset(flag,true,sizeof(flag));
pri[1]=2;
k=1;
for(i=4;i<=10000;i+=2)
flag[i]=false;
for(i=3;i<=10000;i+=2)
if(flag[i]){
pri[++k]=i;
for(int j=i*2;j<=10000;j+=i)
flag[j]=false;
}
return 0;
}
int main(){
int i,j;
int n,ans,sum;
get_pri();
while(scanf("%d",&n),n){
ans=0;
int x=n/2;
for(i=1;pri[i]<=x;i++){
sum=0;
for(j=i;j<=x;j++){
sum+=pri[j];
if(sum==n){
ans++;
break;
}
if(sum>n)
break;
}
}
if(flag[n])
ans++;
printf("%d\n",ans);
}
return 0;
}
ZOJ (3497 Mistwald 关于矩阵求点直接连通的问题)
题目大意：给你一个N*M 的矩阵， 矩阵里的每个点代表一个全送阵， 代表当前点可以全送到4个点，你的出发点是（1，1）；要到达的点是（n,m），这里要注意的是，一旦任何点到了（n,m）点之后 就会被全送出去，离开整个地图，所以这里算是一个陷阱，您要把（n,m）点能够到达的点，全部置0，（”0“代表他不能到达某个点）
题目分析：
这里是Maxtrix67 大牛总结的 第八个矩阵的经典应用:
给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把 给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就 等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的 路径数，我们只需要二分求出A^k即可;
题目让我们求的是他们是否连通，这里只需用1与0带入即可，
我们这里在乘的过程不是求和，而是用到“与”操作，因为我们要得出的结果不是路径数，而是 是否能经过K步到达该点～
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
int s[30][30];
};
struct M unit;
int n;
struct M multiply(struct M a,struct M b){
struct M c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
c.s[i][j]=0;
for(int k=1;k<=n;k++)
//：注意下面这个操作，是“|”而不是“+”这里是求是否能到达
//而不是求 到达的路径数目！
c.s[i][j]=(c.s[i][j]|a.s[i][k]*b.s[k][j]);
}
return c;
}
struct M paw(struct M a,int t){
struct M ans=unit;
struct M b=a;
while(t){
if(t%2==1)
ans=multiply(ans,b);
b=multiply(b,b);
t/=2;
}
return ans;
}
int main(){
struct M a;
memset(unit.s,0,sizeof(unit.s));
char str[100];
int num[10];
for(int i=1;i<=30;i++)
unit.s[i][i]=1;
int h,z,p,cas,t;
int s,e,i,j,k;
scanf("%d",&cas);
while(cas--){
memset(a.s,0,sizeof(a.s));
scanf("%d %d",&h,&z);
n=h*z;
for(i=1;i<=h;i++)
for(j=1;j<=z;j++){
scanf("%s",str);
sscanf(str,"((%d,%d),(%d,%d),(%d,%d),(%d,%d))",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6],&num[7],&num[8]);
s=(i-1)*z+j;
for(k=1;k<=8;k+=2){
e=(num[k]-1)*z+num[k+1];
a.s[s][e]=1;
}
}
//：转换成邻接矩阵后，a.s[n][]就是
//代表原来地图里的[n][m]点与其他点的链接状态
//因为题意说，凡是到了[n][m]点之后，就会马上
//全送出去，离开这个地图，所以我们要把[n][m]到其他点的
//状态值都赋为0！
for(i=1;i<=n;i++)
a.s[n][i]=0;
scanf("%d",&p);
while(p--){
scanf("%d",&t);
struct M c=paw(a,t);
if(c.s[1][n]==0)
printf("False\n");
else{
int x;
for(x=1;x<=n;x++){
if(c.s[1][x]==1)
break;
}
if(n==x)
printf("True\n");
else
printf("Maybe\n");
}
}
printf("\n");
}
}
HDU （1683 纪念SlingShot ）
题目：已知 F（n）=3 * F（n-1）+2 * F（n-2）+7 * F（n-3），n>=3，其中F（0）=1，F（1）=3，F（2）=5，对于给定的每个n，输出F（0）+ F（1）+ …… + F（n） mod 2009。
题目分析：这里我们推出S[N]=S[N-1]+F[N];
F[N]=3*F[N-1] +2*F[N-2] +7*F[N-3];
首先我们要知道这点，我们这里在第推计算 F[n]的同时，也要计算出 S[N];
所以您要构造出一个矩阵 把S[N] F[N] 同时收录计算，在这里我构造的矩阵 如下：
由于第一写了很多，完成文章的时候莫名其妙的 成了空白，所以第二次 我没上次那么仔细分析了
您有不懂的 或者指点的地方 请留言 我立即修正 或者给您答疑：
模拟计算过程的矩阵;
1 3 2 7
0 3 2 7
0 1 0 0
0 0 1 0
初始状态的矩阵：
9 0 0 0
5 0 0 0
3 0 0 0
1 0 0 0
还有构造一个单位矩阵 unit用来 二分计算 {^_^}
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
int s[5][5];
};
struct M unit,tempt,res;
struct M multiply(struct M a,struct M b){
struct M c;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++){
c.s[i][j]=0;
for(int k=1;k<=4;k++)
c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%2009)%2009;
}
return c;
}
struct M paw(int t){
struct M ans=unit;
struct M a=tempt;
struct M b=res;
while(t){
if(t%2==1)
ans=multiply(ans,a);
a=multiply(a,a);
t/=2;
}
b=multiply(ans,b);
return b;
}
int main(){
int f[5];
f[1]=1; f[2]=3; f[3]=5;
f[4]=28;
memset(unit.s,0,sizeof(unit.s));
memset(res.s,0,sizeof(res.s));
memset(tempt.s,0,sizeof(tempt.s));
for(int i=1;i<=4;i++)
unit.s[i][i]=1;
tempt.s[1][1]=1; tempt.s[1][2]=3;
tempt.s[1][3]=2; tempt.s[1][4]=7;
tempt.s[2][2]=3; tempt.s[2][3]=2;
tempt.s[2][4]=7; tempt.s[3][2]=1;
tempt.s[4][3]=1;
res.s[1][1]=9; res.s[2][1]=5;
res.s[3][1]=3; res.s[4][1]=1;
int cas,t,k;
scanf("%d",&cas);
for(k=1;k<=cas;k++){
scanf("%d",&t);
t++;
if(t<=3){
int sum=0;
for(int i=1;i<=t;i++)
sum+=f[i];
printf("Case %d: %d\n",k,sum);
continue;
}
struct M c=paw(t-3);
printf("Case %d: %d\n",k,c.s[1][1]);
}
return 0;
}
FZU 1692(Key problem)
题目分析： 首先题目大意是，有n个小孩，初始时每个人有ai个苹果。现在要进行m轮游戏。每进行一轮游戏，第i个小孩的苹果增加
( R*A(i+n-1)%n+L*A(i+1)%n )个，求进行m轮游戏后，每个小孩有多少个苹果。（0<=m<=10^9,结果模M后输出，1<=M<=10^6）！注意原题目的公式是错的，害的我郁闷了好久～真的 faint！
思路分析：
这些都属于 循环同构的矩阵 计算的一个巧妙的算法就是，只算第一行，然后接下来的只要平移一个单位到下面，然后复制！
做这种题目还是要首先构造出一个矩阵 模拟他的递归过程！
我这里构造的矩阵是：
1 L .... R
R 1 L.. 0
0 R 1 L..0
L..... 0 R 1
然后递归多少次，我只要把这个矩阵乘多少次就可以了，这样做的高效远远优于递归的!
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M{
int s[101][101];
};
int n,p,t;
struct M tempt,unit,res;
//计算矩阵的幂的时候，因为我要计算的矩阵是 循环同构的
//所以只需要计算第一行，其他的N-1行只需要帮他上面一行的
//结果平移一个单位，然后再复制下来就OK啦！
struct M multiply(struct M a,struct M b){
struct M c;
int i,j,k;
for(i=1;i<=1;i++)
for(j=1;j<=n;j++){
c.s[i][j]=0;
for(k=1;k<=n;k++){
if(a.s[i][k]&&b.s[k][j])
c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
}
}
for(i=2;i<=n;i++){
c.s[i][1]=c.s[i-1][n];
for(j=2;j<=n;j++)
c.s[i][j]=c.s[i-1][j-1];
}
return c;
}
struct M multiply2(struct M a,struct M b){
struct M c;
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=1;j++){
c.s[i][j]=0;
for(k=1;k<=n;k++){
if(a.s[i][k]&&b.s[k][j])
c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
}
}
return c;
}
void paw(){
struct M ans=unit;
int i,j;
struct M a=tempt;
while(t){
if(t%2==1)
ans=multiply(ans,a);
a=multiply(a,a);
t/=2;
}
res=multiply2(ans,res);
}
int main(){
int cas,l,r,i,j;
int sim[102];
memset(unit.s,0,sizeof(unit.s));
for(i=1;i<=100;i++)
unit.s[i][i]=1;
cin>>cas;
while(cas--){
memset(res.s,0,sizeof(res.s));
memset(tempt.s,0,sizeof(tempt.s));
scanf("%d %d %d %d %d",&n,&t,&r,&l,&p);
for(i=1;i<=n;i++)
scanf("%d",∼[i]);
for(j=1,i=n;i>=1;j++,i--){
res.s[j][1]=sim[i];
}
tempt.s[1][1]=1; tempt.s[1][2]=l;
tempt.s[1][n]=r;
for(i=2;i<=n;i++){
tempt.s[i][1]=tempt.s[i-1][n];
for(j=2;j<=n;j++)
tempt.s[i][j]=tempt.s[i-1][j-1];
}
paw();
for(i=n;i>1;i--)
printf("%d ",res.s[i][1]);
printf("%d",res.s[i][1]);
printf("\n\n");
}
}
HDU (2276 Kiki & Little Kiki 2 )
题目大意：题目大意给定一系列灯的初始状态，0代表暗，1代表亮，每一秒所有的灯都有可能发生状态切换，
切换规则：当前灯的左边第一个灯是亮的，则当前的灯切换状态，如果当前灯的左边第一盏灯是暗的，则当前灯的状态无需变化！
注意：最左边的参考左右边那栈灯。
题目分析;
首先有两种情况：
左边第一盏灯亮的：
当前灯的动作: 1->0; 0->1;
左边第一盏灯暗的：
当前灯的动作：
1->1; 0->0;
我们可以看到的是， 可以用一个方程来模拟这个过程： F[i] = ( f [ i] +f [i+n-2]%n+1 )%2;
所以我们只要计算这个值就OK啦。
然后由于数据过大，开数组肯定会爆掉～
这里我们要想到的是 矩阵是一个模拟递归的高效算法
这里我们要构造一个 可以计算如上的方程的矩阵：
1 0 0...0 1
1 1 0...0 0
0 1 1..0 0
0 0 1..0 0
. . . 0 ....
. . .0.....
0 0 0..0 1
然后再把f[n]...到f[1]构成一个矩阵和他相乘，正好就是达到了表达式的效果。如果还有不懂的那请您留言，我这里画图不方便悲剧的很
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char sim[102];
struct M{
int s[101][101];
};
struct M unit,res,tempt;
int n,t;
struct M multiply(struct M a,struct M b){
struct M c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
c.s[i][j]=0;
for(int k=1;k<=n;k++)
c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%2)%2;
}
return c;
}
void paw(){
struct M ans=unit;
struct M a=tempt;
while(t){
if(t%2==1)
ans=multiply(ans,a);
a=multiply(a,a);
t/=2;
}
res=multiply(res,ans);
}
int main(){
int i,j,k;
memset(unit.s,0,sizeof(unit.s));
for(i=1;i<=100;i++)
unit.s[i][i]=1;
while(scanf("%d %s",&t,sim)!=EOF){
memset(tempt.s,0,sizeof(tempt.s));
memset(res.s,0,sizeof(res.s));
k=strlen(sim);
n=k;
for(i=1;i<=k;i++)
res.s[1][i]=sim[k-i]-'0';
for(i=1;i<=n;i++){
if(i!=n)
tempt.s[i][i]=tempt.s[i+1][i]=1;
else
tempt.s[1][n]=tempt.s[n][n]=1;
}
paw();
for(int i=n;i>=1;i--)
printf("%d",res.s[1][i]);
printf("\n");
}
return 0;
}
HDU 1757（A Simple Math Problem）
题目分析：
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
这里就是构造一下矩阵 然后依然是矩阵的多次幂 我前面说的很详细，如果看的不清楚可以看我别的文章
构造一个矩阵
就求a^(t-9)*b
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
int s[11][11];
};
int n,p;
struct M multiply(struct M a,struct M b){
struct M c;
memset(c.s,0,sizeof(c.s));
for(int i=1;i<=10;i++)
for(int j=1;j<=10;j++)
for(int k=1;k<=10;k++)
c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
return c;
}
struct M paw(struct M a,int t){
if(t==1)
return a;
else{
struct M b=paw(a,t/2);
if(t&1){
return multiply(multiply(b,b),a);
}
else
return multiply(b,b);
}
}
int main(){
struct M a,b,c;
int t;
memset(a.s,0,sizeof(a.s));
memset(b.s,0,sizeof(b.s));
for(int i=1;i<=10;i++)
b.s[i][1]=10-i;
for(int i=2;i<=10;i++)
a.s[i][i-1]=1;
while(scanf("%d %d",&t,&p)!=EOF){
for(int i=1;i<=10;i++)
scanf("%d",&a.s[1][i]);
if(t<=9){
printf("%d\n",t);
continue;
}
c=paw(a,t-9);
c=multiply(c,b);
printf("%d\n",c.s[1][1]);
}
return 0;
}
HDU （1575 Tr A）
题目分析：Tr A表示方阵A的迹（主对角线元素之和），求Tr(Ak) % 9973。
由于k最大有10^9，所以只能用矩阵二分快速幂得到Ak，最后求和即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
int s[11][11];
};
int n,p=9973;
struct M multiply(struct M a,struct M b){
struct M c;
memset(c.s,0,sizeof(c.s));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
return c;
}
struct M paw(struct M a,int t){
if(t==1)
return a;
else{
struct M b=paw(a,t/2);
if(t&1){
return multiply(multiply(b,b),a);
}
else
return multiply(b,b);
}
}
int main(){
struct M a,b;
int k,sum,cas;
cin>>cas;
while(cas--){
scanf("%d %d",&n,&k);
sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a.s[i][j]);
/*for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
printf("%d",a.s[i][j]);*/
b=paw(a,k);
for(int i=1;i<=n;i++)
sum=(sum+b.s[i][i])%p;
printf("%d\n",sum);
}
return 0;
}