AOJ1310 Find the Multiples

AOJ Volume13

問題リンク Find the Multiples

  • 概要

a_0 〜 a_(n-1)の[0,9]の列と素数Qが与えられる。i <= jでかつa_i≠0であるような部分列
a_i a_(i+1) ... a_j
を10進数の正の整数とみなす。リーディング0なものは認めない。この正の整数がQの倍数であるような(i, j)の組がいくつあるか答えよ。答えは2^30を超えない。
a_0 ... a_(n-1)の列は問題文にあるプログラム片で求めること。
1 <= N <= 10^5
Q < 10^8 && prime

  • 解法

(i, j)の部分列a_i...a_jは
a_i a_(i+1) ... a_(n-1) - a_(j+1) a_(j+2) ... a_(n-1)
という引き算と同じことになります。ここで、もし
{ a_i a_(i+1) ... a_(n-1) } mod Q - { a_(j+1) a_(j+2) ... a_(n-1) } mod Q
が0になったとき、つまり、両式のmod Qが同じだったとき且つこのときに限り、部分列a_i ... a_jはQの倍数になります( X = A - B ⇒ X mod Q = A mod Q - B mod Q で右辺が0になっているから)。なので、A_i = a_i ... a_(n-1) mod Qを各iについて求め、i < jでA_i mod Q = A_j mod Q が等しいものがいくつあるかをカウントすれば解けます。A_iをA_(i+1)から求めるために
A_i = ( a[i] * 10^k + A_(i+1) ) mod Q (kは適切な値)
として計算しました。10^kの部分は適宜mod Qを取っていけばオーバーフロー地獄になることはありません。
10^k のところでmod Qを使うので、Qが2や5だとうまく計算できません。ですが、Qが2や5の場合、部分列の一番下の数字だけで、Qの倍数が判定できるので心配ありません。

追記
すっごい怪しい議論をしていることに気付いた。
X = a_i ... a_j
A = a_i ... a_(n-1)
B = a_(j+1) ... a_(n-1)
A - Bの引き算って
a_i ... a_j 0 0 ... 0
っていう形になるから
X = A - B
じゃなくて
X * 10^(n-j-1) = A - B
になる。でも正しい答えが求まってたのはなぜだろう。
これで、A mod Q - B mod Q = 0のとき、
X * 10^(n-j-1) mod Q = A mod Q - B mod Q
X * 10^(n-j-1) mod Q = 0
で、Qは素数で、Qが2や5でない場合この合同式が成り立つためには、
X mod Q = 0
しかないからうまく答えが求まってた感じかな？

  • ソース
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//Find the Multiples
public class AOJ1310 {

	Map<Integer, Integer> cnt;
	void inc(int m){
		if(cnt.containsKey(m))cnt.put(m, cnt.get(m)+1);
		else cnt.put(m, 1);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), S = sc.nextInt(), W = sc.nextInt(), Q = sc.nextInt();
			if((n|S|W|Q)==0)break;
			int[] a = new int[n];
			int g = S;
			for(int i=0;i<n;i++){
				a[i] = (g/7) % 10;
				if((g&1) == 0)g>>=1;
				else g = (g>>1) ^ W;
			}
			int res = 0;
			if(Q==2){
				int e = 0;
				for(int i=n-1;i>=0;i--){
					if((a[i]&1)==0)e++;
					if(a[i]!=0)res+=e;
				}
			}
			else if(Q==5){
				int f = 0;
				for(int i=n-1;i>=0;i--){
					if(a[i]==0||a[i]==5)f++;
					if(a[i]!=0)res+=f;
				}
			}
			else{
				cnt = new HashMap<Integer, Integer>();
				inc(0);
				int ten = 1, m = a[n-1]%Q;
				inc(m);
				if(m==0 && a[n-1]!=0)res++;
				for(int i=n-2;i>=0;i--){
					ten = (ten*10)%Q;
					m = (a[i]*ten+m)%Q;
					if(a[i]!=0 && cnt.containsKey(m))res+=cnt.get(m);
					inc(m);
				}
			}
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new AOJ1310().run();
	}
}