AOJ-1310: Find the Multiples

keyword

整数　素数　Java

問題概要

長さN(<10^5)の0-9からなる文字列が与えられる。素数Q(<10^8)の正の倍数となるようなleading 0でない部分文字列が何通りあるか求める問題。答えはsigned intにおさまることが保証されている。

解法

文字列をa[0]a[1]..a[N-1]とする。b[i] = a[i]a[i+1]..a[N-1] (10進の数値として解釈)とすると、b[i]=b[j] (mod Q)ならb[i]-b[j]=a[i]a[i+1]..a[j-2]a[j-1]0..0 (10進の数値として解釈)はQの倍数。ここで、Qと10が互いに素ならa[i]a[i+1]..a[j-2]a[j-1] (10進の数値として解釈)もQの倍数。なのでQが2,5以外の時は後ろから数えていけばいいことが分かる。Qが2,5の場合は最後の桁だけ着目すれば良いので簡単。

感想

今考えるとものすごく自然なのに解いてるときは中々思いつかなかった。その原因はいつも前から累積和をとっていることだと思う。Horner法っぽく前から考える発想から抜けだせなかった。以下のソースは思考の過程みたいのが所々に残って非常に汚い(無意味な計算がたくさんある)。

import java.util.*;

public class Main {

	int N, Q;
	int[] as;

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			int S, W;
			N = in.nextInt();
			S = in.nextInt();
			W = in.nextInt();
			Q = in.nextInt();
			if(N==0) return ;
			as = new int[N];
			int g = S;
			for(int i=0; i<N; i++){
				as[i] = (g/7)%10;
				if(g%2 == 0){
					g = g/2;
				}
				else{
					g = (g/2) ^ W;
				}
			}
			System.out.println(solve());
		}
	}

	int subsolve(){
		int ans = 0;
		boolean[] oks = new boolean[10];
		if(Q==2){
			oks[0] = oks[2] = oks[4] = oks[6] = oks[8] = true;
		}
		else{
			oks[0] = oks[5] = true;
		}
		int accum = 0;
		for(int i=0; i<N; i++){
			if(as[i] > 0){
				accum++;
			}
			if(oks[as[i]]){
				ans += accum;
			}
		}
		return ans;
	}

	int solve(){
		if(Q==2 || Q==5){
			return subsolve();
		}
		int ans = 0;
		int[] accums = new int[N];
		int ten = 10 % Q;
		accums[N-1] = as[N-1]%Q;
		for(int i=N-2; i>=0; i--){
			accums[i] = (ten * as[i] + accums[i+1])%Q;
			ten = (ten * 10)%Q;
		}
		HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();
		dict.put(0, 1);
		for(int i=N-1; i>=0; i--){
			int sub = accums[i];
			sub = (sub + Q)%Q;
			if(as[i] > 0 && dict.containsKey(sub)){
				ans += dict.get(sub);
			}
			int cur = dict.containsKey(sub)?dict.get(sub):0;
			dict.put(sub, cur+1);
		}
		return ans;
	}

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