「CFgym100541」Treasure Box

2015年3月14日2,8800

Your team was exploring an ancient city. Suddenly you found an old scroll with 2 integer numbers N and K, which encrypts the secret code to open a treasure box. Considering a transformation on an integer Xdescribed as follows:

X = X + X mod 100,

the secret code can be obtained by applying the above-described transformation K times successively to N.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 500.

Each dataset has two space-separated positive integers N and K (1 ≤ N ≤ 10⁹, 1 ≤ K ≤ 10⁹) written on a single line.

Output

For each dataset, write on a single line the secret number decrypted from N and K.

Sample test(s)

input

2
31102014 2
10101 10

31102014 2

10101 10

output

31102056
10324

1 2	31102056 10324

题解

x转换y次的增加值和x%100转换y次相同

预处理0-99转换1-50000次的答案

就能每50000一次转移了。。。

或者倍增也可以

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define mod 1000000009
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T;
ll val[105][50005];
ll dp(ll x,ll y)
{
    if(y==0)return x;
    if(val[x][y]!=-1)return val[x][y];
    int t=0;
    if(x+x>=100)t=100;
    return val[x][y]=t+dp((x+x)%100,y-1);
}
ll solve(ll x,ll y)
{
    ll ans=0;
    ans=x/100*100;x%=100;
    for(int i=1;i<=y/50000;i++)
    {
        ll t=dp(x,50000);
        ans+=t/100*100;
        x=t%100;
    }
    y%=50000;
    return ans+dp(x,y);
}
int main()
{
    
    memset(val,-1,sizeof(val));
    T=read();
    while(T--)
    {
        ll x=read(),y=read();
        printf("%I64d\n",solve(x,y));
    }
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define mod 1000000009

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T;

ll val[105][50005];

ll dp(ll x,ll y)

{

if(y==0)return x;

if(val[x][y]!=-1)return val[x][y];

int t=0;

if(x+x>=100)t=100;

return val[x][y]=t+dp((x+x)%100,y-1);

}

ll solve(ll x,ll y)

{

ll ans=0;

ans=x/100*100;x%=100;

for(int i=1;i<=y/50000;i++)

{

ll t=dp(x,50000);

ans+=t/100*100;

x=t%100;

}

y%=50000;

return ans+dp(x,y);

}

int main()

{

memset(val,-1,sizeof(val));

T=read();

while(T--)

{

ll x=read(),y=read();

printf("%I64d\n",solve(x,y));

}

return 0;

}

« 「BZOJ2796」[POI2012] Fibonacci Representation 「BZOJ3208」花神的秒题计划Ⅰ »

hzwer.com _ Home | http://hzwer.com

「CFgym100541」Treasure Box

分类目录

热门文章

Myfriends

近期评论