pku2649.java

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· Java 代码 · 共 63 行

import java.io.*;
import java.util.*;
import java.math.BigInteger;

class Main
{
	public static void main(String args[]) throws Exception
	{
		Scanner cin=new Scanner(System.in);
		int n, m, mt, i;
		while(cin.hasNext())
		{
			n = cin.nextInt();
			m = cin.nextInt();
			mt = m;
			
			if (m == 0)
			{
				System.out.printf("%d does not divide %d!\n", m, n);
				continue;
			}

			if (n >= m)
			{
				System.out.printf("%d divides %d!\n", m, n);
				continue;
			}
			else if (BigInteger.valueOf(m).isProbablePrime(10))
			{
				System.out.printf("%d does not divide %d!\n", m, n);
				continue;
			}
			
			
			for(i = 2; i <= n && mt > 1; i++)
			{
				mt /= gcd(mt, i);
			}
			if (mt == 1)
			{
				System.out.printf("%d divides %d!\n", m, n);
			}
			else
			{
				System.out.printf("%d does not divide %d!\n", m, n);
			}
		}
	}
	
	static int gcd(int a, int b)
	{
		int tmp;
		while (b != 0)
		{
			a = a % b;
			tmp = a;
			a = b;
			b = tmp;
		}
		return a;
	}
}