ICPC/Regional/2010F

出展 †

• ICPCアジア地区予選 東京大会 2010 問題文(AOJ)

解法 †

• Qが2または5のとき
  • i番目の桁を先頭とする数のうちQで割り切れるものの個数は，aj%Q==0となるj(>i)の数
• それ以外
  • tiをai, ai+1, ..., aN-1を並べた数とする
  • tiをQで割った余りがtj(j>i)をQで割った余りと等しいとき，ai, ..., aj-1を並べた数はQで割り切れる
  • Qが素数であるから，この場合は2と5を約数に持たないため
• 以上を利用して，下の桁から見て個数を数えていけば良い

回答 †

• 2010F_pes.cpp - mapを使って素直目に(pes)