2013金山西山居クリエイティブゲームプログラムチャレンジレース-初戦(2)hdu 4548 4549 4550

A題水題.直接暴力素数表.そして1から美素数の個数の計算を行います.
c[n]は1−nから中米素数の個数を記録する.
HDu 4548コード

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
bool flag[1000010];
int c[1000010];
void init()
{
    int i,j,k;
    memset(flag,0,sizeof(flag));
    for(i = 2;i < 1000001; i++)
    {
        if(!flag[i])
        {
            for(j = i+i;j < 1000001;j+=i)
                flag[j] = true;
        }
    }
}
bool check(int n)
{
    int tmp = 0;
    while(n)
    {
        tmp += n%10;
        n /= 10;
    }
    if(flag[tmp] == false)    return true;
    else            return false;
}
int main()
{
    init();
    memset(c,0,sizeof(c));
    c[2] = 1;c[3] = 2;
    for(int i = 4;i<=1000000;i++)
    {
        c[i] = c[i-1];
        if(flag[i] == false && check(i))
            c[i]++;
    }
    int n,m;
    int T,cas = 0;;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        printf("Case #%d: %d
",++cas,c[m] - c[n-1]);
    }
    return 0;
}

B問題は、式を推定しやすい.
F[n] = (a^m1)*(b^m2)
fibonacci配列をfibとする.m 1=fib[n−1],m 2=fib[n],n=0または1の場合に特に判定する.
フェルマの定理:

 a^fib[n - 1] = a^(fib[n - 1]%1000000006) (mod 1000000007)

b^fib[n] = b^(fib[n]%1000000006) (mod 1000000007)

        。 fib      ，         。
hdu 4549   ：

 
  
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define llg long long
const llg mod = 1000000007;
struct matrix
{
	llg a[2][2];
	void init()
	{
		a[0][0] = a[0][1] = a[1][0] = a[1][1] = 1;
		a[1][1] = 0;
	}
};
matrix mul1(matrix tmp1,matrix tmp2)
{
	matrix ans;
	for(int i = 0;i<2;i++)
		for(int j = 0;j<2;j++)
		{
			ans.a[i][j] = 0;
			for(int k = 0;k<2;k++)
			{
				ans.a[i][j] += (tmp1.a[i][k]*tmp2.a[j][k])%(mod - 1);
				ans.a[i][j] %= (mod - 1);
			}
		}
	return ans;
}
llg mul2(matrix tmp,llg n)
{
	matrix ans;
	ans.init();
	while(n)
	{
		if(n&1) ans = mul1(ans,tmp);
		tmp = mul1(tmp,tmp);
		n>>=1;
	}
	return ans.a[1][1];
}

llg q_mod(llg a,llg n)
{
	llg ans = 1;
	matrix tmp2;
	tmp2.init();
	llg nn = mul2(tmp2,n);
	nn %= (mod - 1);
//cout<>=1;
	}
	return ans%mod;
}
int main()
{
	llg a,b,n;
	while(cin >> a >> b >> n)
	{
		if(n == 0)	{cout<
  
c ，         ，     ，         。        。
  
hdu 4550   ：
  
 
  
#include
#include
#include
using namespace std;
#define llg long long
int main()
{
	int T;
	char s[110];
	string a;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",s);
		int len = strlen(s);
		a = s[0];
		char minc = '9' + 1;
		int index = 0;
		for(int i = 0;i < len;i++)
		{
			if(s[i] != '0')
			{
				if(minc >= s[i])
				{
					minc = s[i];
					index = i;
				}
			}
		}
		for(int i = 1;i < len;i++)
		{
			if(i == index)	a = s[i] + a;
			else
			{
				if(i > index)	a = a + s[i];
				else
				{
					if(s[i] > a[0])	a = a + s[i];
					else			a = s[i] + a;
				}
			}
		}
		cout<