UVA 12627 Eratic Expansion
942 ワード
テーマリンク:http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&page=show_problem&problem=4352
問題解決の考え方:
法則問題を求める。再帰的に解く。
ACコード:
問題解決の考え方:
法則問題を求める。再帰的に解く。
ACコード:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll num[35],l[35];
int n;
ll fun(int k,int x)
{
if(x==0)
return 0;
if(x==l[k])
return num[k];
else
{
if(x>l[k-1])
return fun(k-1,x%l[k-1])+2*num[k-1];
else
return 2*fun(k-1,x);
}
}
int main()
{
int i,j;
num[0]=1;l[0]=1;
for(i=1;i<=30;i++)
{
num[i]=3*num[i-1];
l[i]=2*l[i-1];
}
int T,tt=1;
scanf("%d",&T);
while(T--)
{
int a,b;
scanf("%d%d%d",&n,&a,&b);
printf("Case %d: %lld
",tt++,fun(n,b)-fun(n,a-1));
}
return 0;
}