首页 > 试题广场 >

平方根问题

[编程题]平方根问题

热度指数：683 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

考虑定义在两正整数上的函数SSR(平方根之和的平方):SSR(A, B) = (sqrt(A) + sqrt(B))^2。牛牛对函数值为整数的情况很感兴趣。现在给定整数n和m,请帮助牛牛计算有序对(A, B)的数量, 满足1 ≤ A ≤ n, 1 ≤ B ≤ m而且SSR(A, B)是一个整数。

输入描述:

输入包括两个整数n和m(1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5)

输出描述:

输出一个整数,表示满足条件的有序对对数。

示例1

输入

3 8

输出

算法知识视频讲解

元气の悟空

#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int prime[MAXN+1],factor[100][2];
void getPrime();
int getFactors(int);
int main(){
    int n,m,res=0,i;
    getPrime();
    scanf("%d%d",&n,&m);
    map<int,int> mpn,mpm;
    for(i=1;i<=n;i++) mpn[getFactors(i)]++;
    for(i=1;i<=m;i++) mpm[getFactors(i)]++;
    map<int,int>::iterator it;
    for(it=mpn.begin();it!=mpn.end();it++)
        if(mpm.count(it->first))
            res+=it->second*mpm[it->first];
    printf("%d",res);
}
void getPrime(){
    for(int i=2;i<=MAXN;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int getFactors(int x){
    int fatCnt=0,tmp=x,res=1,i;
    for(i=1;prime[i]<=tmp/prime[i];i++){
        factor[fatCnt][1]=0;
        if(tmp%prime[i]==0){
            factor[fatCnt][0]=prime[i];
            while(tmp%prime[i]==0){
                factor[fatCnt][1]++;
                tmp/=prime[i];
            }
            fatCnt++;
        }
    }
    if(tmp!=1){
        factor[fatCnt][0]=tmp;
        factor[fatCnt++][1]=1;
    }
    for(i=0;i<fatCnt;i++)
        if(factor[i][1]%2) res*=factor[i][0];
    return res;
}

发表于 2017-12-01 12:40:01 回复(1)

自从厌倦于追寻

看了下面这位大神的代码……大概应该是先用素数打表（而且是高效的素数打表）找出范围内所有的素数，然后找出1~m内，每个数，他的所有素数因子中个数为单数的积（比如18 = 2 * 3 * 3，2出现一次，为单数次，所以是2；10 = 2 * 5，2和5都只出现一次，所以是2 * 5 = 10）的集合mpm和1~n同样的集合mpn。 (sqrt(A) + sqrt(B))^2可以化简为A + B + 2*sqrt(A*B)，所以其实就是要2*sqrt(A*B)为整数，也就是A*B开根号后是整数，也就是A*B可以拆成a*a*b*b这样的形式，也就是每个素因子的个数都是双数的。对于数字18，它出现单数次的素因子是2，所以它要乘以一个同样是只有一个单数次素因子2的数，结果开根号才可以是整数。所以答案就是当x表示范围内所有素数，mpn中单数素因子为x的数字个数*mpn中单数素因子个数为x的数字个数，最后求和。个人理解……

编辑于 2017-12-03 07:24:50 回复(0)

Java

hsp619

import java.util.Scanner;

public class test3 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int num=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int A=(int)(Math.sqrt(i*j));
                if(A==Math.sqrt(i*j)){
                    num++;
                }
            }
        }
        System.out.println(num);
    }
}

发表于 2019-03-16 15:13:36 回复(0)

Brief199595

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int m=sc.nextInt();
    int num=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int A=(int) (Math.sqrt(i*j));
            if(A==Math.sqrt(i*j)){
                num++;
            }
        }        
    }
    System.out.println(num);


}

}
通过率60%。超时了。

发表于 2018-08-25 22:04:23 回复(0)

neviety


import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        int n=scan.nextInt();
        int m=scan.nextInt();
        int cnt=0;
        double a,b;
        double sum;
        int  temp;
        double result;
        for(int i=1;i<=n;i++){
            a=Math.sqrt(i);
            for(int j=1;j<=m;j++){
                b=Math.sqrt(j);
                System.out.println(a+" "+b);
                sum=a+b;
                result= Math.pow(sum, 2);
                temp=(int ) result;
                if(result==temp)
                    cnt++;
            }

        }

        System.out.println(cnt);

    }

}

为什么我的暴力求解不对呢，简单的测试用例2,2 3,8 都不对实在想不出漏了什么情况啊

发表于 2018-08-23 21:03:17 回复(1)

哎呀妈呀，真香

哪位大神能说一下，怎样判断一个数是不是整数。

发表于 2018-05-21 11:08:39 回复(4)

风林火山_kelvin

链接：https://www.nowcoder.com/questionTerminal/6524263a0cc9427ebb0af10b3f366774 来源：牛客网

	#include<stdio.h>



	#include<math.h>



	intpend[100005];



	voidgetPend(intm)



	{



	    intrec;



	    for(inti=2,rec=i*i;rec<=m;i++,rec=i*i)



	    {



	        if(pend[rec])continue;



	        for(intj=rec;j<=m;j+=rec)



	        pend[j]=1;



	    }



	}



	intmain()



	{



	    intn,m;



	    scanf("%d%d",&n,&m);



	    intsn=(int)sqrt(n),sm=(int)sqrt(m);



	    longlongans=sn*sm;



	    getPend(n>m?m:n);



	    for(inti=2;;i++)



	    {



	        if(pend[i])continue;



	        if(n/i==0||m/i==0)break;



	        intnt=n/i,mt=m/i;



	        intsnt=(int)sqrt(nt),smt=(int)sqrt(mt);



	        ans+=snt*smt;



	    }



	    printf("%lld",ans);



	    return0;



	 



	   }

发表于 2018-05-11 11:18:36 回复(0)

SKForever



	import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;



	public class Main{
 public static int MAX_VALUE;
 public static void solve(){
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int m = sc.nextInt();
  
  if(n>=m) MAX_VALUE = n;
  else MAX_VALUE = m;
  
  boolean[] primeList = new boolean[MAX_VALUE+1];
  ArrayList<Integer> list1 = new ArrayList<>();
  ArrayList<Integer> list2 = new ArrayList<>();
  ArrayList<Integer> primes = new ArrayList<>();
  int[] countlist1 = new int[n+1];
  int[] countlist2 = new int[m+1];
  primeList[1] = true;
  for(int i=2;i<=Math.sqrt(MAX_VALUE);i++){
   for(int j=i*2;j<=MAX_VALUE;j+=i){
    primeList[j] = true;
   }
  }
  
  for(int i=1;i<=MAX_VALUE;i++){
   if(!primeList[i])
   {
    primes.add(i);
   }
  }



	  helper(n,list1,countlist1,primes);
  //System.out.println("");
  helper(m,list2,countlist2,primes);
  //System.out.println("");



	  int result = 0;
  int min = m;
  if(n<m){
   min = n;
  }
  for(int i=2;i<=min;i++){
   result += countlist1[i]*countlist2[i];
  }
  
  int count1 = (int) Math.sqrt(n);
  int count2 = (int) Math.sqrt(m);
  result+= count1*count2;
  
  System.out.println(result);
 }
 
 private static void helper(int n,ArrayList<Integer> list,int[] countlist,ArrayList<Integer> primes){
  for(int i=2;i<=n;i++){
   int result = 1;
   int curr = i;
   for(Integer prime: primes){
    if(prime>curr) break;
    if(curr%prime==0){
     if(curr%(prime*prime)==0){
      int walk = curr;
      int times = 0;
      while(walk>1 && walk%prime==0){
       times++;
       walk = walk/prime;
       curr = curr/prime;
      }
      if(times%2==1){
       result*=prime;
      }
     }
     else{
      result*=prime;
      curr /= prime;
     }
    }
   }
   
   if(result!=1)
   {
    list.add(result);
    countlist[result]++;
    //System.out.print(result+" ");
   }
   result = 1;
  }
 }
    public static void main(String[] args){
        solve();
    }
}

发表于 2018-04-25 11:24:45 回复(0)

pb1998

 #include<stdio.h>
 #include<math.h>
 int pend[100005];
 void getPend(int m)
 {
     int rec;
     for(int i=2,rec=i*i;rec<=m;i++,rec=i*i)
     {
         if(pend[rec]) continue;
         for(int j=rec;j<=m;j+=rec)
         pend[j]=1;
     }
 }
 int main()
 {
     int n,m;
     scanf("%d%d",&n,&m);
     int sn=(int)sqrt(n),sm=(int)sqrt(m);
     long long ans=sn*sm;
     getPend(n>m?m:n);
     for(int i=2;;i++)
     {
         if(pend[i]) continue;
         if(n/i==0||m/i==0) break;
         int nt=n/i,mt=m/i;
         int snt=(int)sqrt(nt),smt=(int)sqrt(mt);
         ans+=snt*smt;
     }
     printf("%lld",ans);
     return 0;

	}



	//个人观点

编辑于 2017-12-14 11:50:57 回复(1)

屠201712061729333

#include <iostream>
#include <map>


int sqare[1010];
int symbol[100100];


int Prefix(const int val) {

    int ans = val;
    for (int i = 1; i <= 1000; ++i) {
        if (sqare[i] > val) {
            break;
        }
        if (val % sqare[i] == 0) {
            ans = std::min(ans,val / sqare[i]);
        }
    }


    return ans;
}


void Init() {

    for (int i = 0; i <= 1000; ++i) {
        sqare[i] = i * i;
    }

    for (int i = 0; i <= 100010; ++i) {
        symbol[i] = Prefix(i);
    }
}


int main()
{
    Init();

    int n,m;
    while (std::cin >> n >> m) {

        int min_value = std::min(n,m);
        int max_value = std::max(n,m);

        std::map<int,int> mp;

        for (int i = 1; i <= min_value; ++i ) {
            ++mp[symbol[i]];
        }

        long long ans = 0;

        for (int i = 1; i <= max_value; ++i) {
            ans += mp[symbol[i]];
        }

        std::cout << ans << std::endl;

    }
    return 0;
}

发表于 2017-12-06 17:45:19 回复(0)