首页 > 代码库 > ZOJ ACM 1314(JAVA)

ZOJ ACM 1314(JAVA)

昨天做了几个题目,过于简单,就不在博客里面写了。

1314这道题也比较简单,写出来是因为我觉得在这里有一个小技巧,对于时间复杂度和空间复杂度都比较节省。

这个题目类似哈希表的求解,但是更简单。刚拿到题目时,我想当然的希望将查询结果放到一个数组里面,然后遍历查询是否有一样的mod值。但是感觉这样肯定是最普遍的方法而且效率也不是太高。

后来想到了其他的一些查询算法,比如二分,但是都感觉不太合适。直到我意识到这个过程和计算哈希表的过程类似,所以直接用mod值作为数组的下标索引,可以直接定位到当前值是否已经被计算过,从而快速判断是否一个好循环。

public class Main {
	
	public static void main(String argv[]) {
		int Step, Mod;
		java.util.Scanner scanner = new java.util.Scanner(System.in);
		while(scanner.hasNext()) {
			String strLine = scanner.nextLine();
			String strNums[] = strLine.split(" ");
			Step = Integer.parseInt(strNums[0]);
			Mod = Integer.parseInt(strNums[1]);
			
			int mods[] = new int[Mod];
			mods[0] = 0;
			int seed = 0;
			String strResult = "Good Choice";
			for(int i=1;i<Mod;i++) {
				seed = (seed + Step) % Mod;
				if(mods[seed] == 0 && seed != 0) {
					mods[seed] = seed;
				}
				else {
					strResult = "Bad Choice";
					break;
				}
			}
			System.out.format("%10s", Step);
			System.out.format("%10s", Mod);
			System.out.println("    "+strResult+"\n");
		}
	}
}