반응형
https://www.acmicpc.net/problem/1009
1009번: 분산처리
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
www.acmicpc.net
1의 자리에 b번을 곱하여 출력하는 방법은 시간초과로 풀 수 없다.
각 자리수마다 반복되는 배열을 구하고 자리수로 접근하여 해결할 수 있다.
using namespace std;
vector< vector >MAP;
int g(int w, int a)
{
return (w*a)%10;
}
void makeMAP()
{
for(int i=0;i<99;i++)
{
MAP.push_back(vector());
int w = (i+1)%10;
MAP[i].push_back(w);
while(1)
{
w = g(w, i+1);
if(MAP[i][0] == w)
break;
else
MAP[i].push_back(w);
}
}
}
int main()
{
makeMAP();
int T;
for(scanf("%d",&T);T>0;T--)
{
int a, b;
scanf("%d %d", &a, &b);
int B = (b % MAP[a-1].size())-1;
if(B<0)
B = MAP[a-1].size()-1;
printf("%d\n", (MAP[a-1][B]==0)?10:MAP[a-1][B]);
}
return 0;
}
반응형