PKU 3652-Persistent Bits

問題概要

X₀=S

X_n=(A×X_n-1+B)%C
で表わされる数列Xの各Bitについて，0しか取らない，1しか取れない，0と1のどちらも取り得るの3種類のうちどれに当て嵌まるか答えよ．

解法

全部試してみる

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner cin;
	String[]res={"!","0","1","?"};
	void run(){
		cin=new Scanner(System.in);
		int A,B,C,S;
		while(true){
			A=cin.nextInt();
			if(A==0)break;
			B=cin.nextInt();
			C=cin.nextInt();
			S=cin.nextInt();
			int[] ans=new int[16];
			Set<Integer> visited=new HashSet<Integer>();
			while(visited.contains(S)==false){
				for(int i=0;i<16;i++){
					if(((S>>i)&1)==0){
						ans[i]|=1;
					}else{
						ans[i]|=2;
					}
				}
				visited.add(S);
				S=(int) ((A*(long)S+B)%C);
			}
			for(int i=15;i>=0;i--){
				printf("%s",res[ans[i]]);
			}
			printf("\n");
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

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

}