NOIP2009提高组 Hankson的趣味题【Java实现】

一、注意点

使用如下题解只能通过8/10个数据

二、题目

三、思路题解

因此当满足上述4个条件时就计数加1

四、能通过8/10数据的代码

import java.util.*;
public class Main{static int gcd(int a,int b){if(b==0){return a;}return gcd(b,a%b);}public static void main(String[] args){Scanner sc = new Scanner(System.in);int t = sc.nextInt();for(int j=0;j<t;j++){int a0 = sc.nextInt();int a1 = sc.nextInt();int b0 = sc.nextInt();int b1 = sc.nextInt();int ans = 0;//用来计数for(int x=1;x*x<=b1;x++){if(b1%x==0&&x%a1==0&&gcd(x/a1,a0/a1)==1&&gcd(b1/b0,b1/x)==1){ans++;}int y = b1/x;//求得另外一个因数if(y==x){//如果两个因数相等，continue，避免重复continue;}else{if(b1%y==0&&y%a1==0&&gcd(y/a1,a0/a1)==1&&gcd(b1/b0,b1/y)==1){ans++;}}}System.out.println(ans);}}
}