模运算 开方二分法.txt

ACM资料大集合

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

//模运算 开方二分法  NOJ 1088
/*
输入
2 3 3
2 3 4

输出
2 
0
*/ 
__int64 cal(__int64 a,__int64 b,__int64 n)
{
	__int64 bb;
	bb=(__int64)sqrt(b);
	//递归式
	//由于b=bb^2+temp,则有a^(bb^2+temp)=(a^b)^b*(a^temp),再加入模运算，得到递归式
	if(b>=2) return (cal(cal(a,bb,n),bb,n)*cal(a,b-bb*bb,n))%n;
	else if(b==1) return a%n;
	else return 1;
}

int main()
{
	__int64 a,b,n;
	while(scanf("%I64d%I64d%I64d",&a,&b,&n)!=EOF)
	{
		printf("%I64d\n",cal(a,b,n));
	}
	return 0;
}



#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <string.h>
using namespace std;

int f[1200][1200];

void cal(char *s1,char *s2)
{
    int i,j;
    int len1=strlen(s1);
    int len2=strlen(s2);
    for(i=0;i<len1;i++)
    {
        for(j=0;j<len2;j++)
            f[i][j]=0;
    }
    for(i=1;i<len1;i++)
    {
        for(j=1;j<len2;j++)
        {
            if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1]+1;
            else
            {
                if(f[i][j-1]<f[i-1][j]) f[i][j]=f[i-1][j];
                else f[i][j]=f[i][j-1];
            }
        }
    }
}