从零开始的算法题生活 (三)

引言

练习的有点频繁了，无奈近来心情太乱，刷刷算法题有益身体健康 ^_^,本次的题是 hihoCoder144 周练习题

描述

小 Hi 最近在追求一名学数学的女生小 Z。小 Z 其实是想拒绝他的，但是找不到好的说辞，于是提出了这样的要求：对于给定的两个正整数 N 和 M，小 Hi 随机选取一个 N 的约数 N'，小 Z 随机选取一个 M 的约数 M'，如果 N'和 M'相等，她就答应小 Hi。

小 Z 让小 Hi 去编写这个随机程序，到时候她 review 过没有问题了就可以抽签了。但是小 Hi 写着写着，却越来越觉得机会渺茫。那么问题来了，小 Hi 能够追到小 Z 的几率是多少呢？

输入

每个输入文件仅包含单组测试数据。

每组测试数据的第一行为两个正整数 N 和 M，意义如前文所述。

对于 40% 的数据，满足 1<=N,M<=106

对于 100% 的数据，满足 1<=N,M<=1012

输出

对于每组测试数据，输出两个互质的正整数 A 和 B（以 A 分之 B 表示小 Hi 能够追到小 Z 的几率）。

样例输入

3 2

样例输出

4 1

##解析
提取关键信息后，本题可抽象为给出两个数，求出一个数约数和另一个约数的所有组合，组合中约数相等的组合占所有组合的比例。
很容易得到以下解题思路:
1、先求出两数约数不同组合个数记为 sum
2，找出相等的组合个数记为 count
3，count/sum,化到最简
代码如下:(gcc6.3.1)

#include<stdio.h>
#include<stdlib.h>
typedef long long LL;
#define max(x,y) x>y?x:y
#define min(x,y) x>y?y:x
LL getCount(LL N,LL * array);
int main(void){
    LL N,M,N1,M1;
    LL count=0;
    LL sum=0;
    LL sum1=0;
    LL temp=0;
    LL i=0;
    LL j=0;
    LL arrayn[100000]={0};
    LL arraym[100000]={0};
    scanf("%lld%lld",&N,&M);
    N1=getCount(N,arrayn);
    M1=getCount(M,arraym);
    sum=N1*M1;
    for(i=1;i<=N1;i++){
	    for(j=1;j<=M1;j++)
        	if(arrayn[i]==arraym[i]){
            		count++;
		}
    }
    temp=max(sum,count);
    while(temp>=1){
        if(sum%temp==0&&count%temp==0){
                    printf("%lld %lld",sum/temp,count/temp);
                    break;
        }
        else temp--;
 
    }
    return 0;
}
LL getCount(LL N,LL *array){
    LL n=N;
    LL count=0;
    LL i;
    LL j;
    if (n%2==0)
    {
        for (i = 1,j=1; i <= n / 2; i++,j++){
            if (n % i == 0){
                array[j]=i;
                count++; 
                
            }
            
        }
	array[n]=1;
	count++;
    }
    if (n%2==1){
        for (i=1,j=1;i<=(n-1)/2;i++,j++){
            if (n % i == 0){
                array[j]=i;
                count++;
                
            }
        }
	array[n]=1;
	count++;
    }
    return count;
}

然而这段代码的运行结果没有通过所有的测试用例，即没有 AC，自己阅读原题后发现对于 100% 的数据，满足 1<=N,M<=10^12,这就很尴尬了，数组大小申请空间肯定不够。又不想去自己实现确保数组申请到那么大的空间，所以想到利用 C++ 中的 map 去搞，，终于 AC，代码如下:

#include<cstdio>
typedef long long LL;
#include<map>
using namespace std;
map<LL,int>arrays;
LL sum=0;
int flag=0;
#define max(x,y) x>y?x:y
#define min(x,y) x>y?y:x
LL getCount(LL N);
int main(void){
    LL N,M,N1,M1;
    LL count=0;
    LL temp=0;
    LL minvalue=0;
    LL i=0;
    scanf("%lld%lld",&N,&M);
    N1=getCount(N);
    M1=getCount(M);
    count=N1*M1;
    minvalue=min(N,M);
    temp=max(sum,count);
    while(temp>=1){
        if(sum%temp==0&&count%temp==0){
                    printf("%lld %lld\n",count/temp,sum/temp);
                    break;
        }
        else temp--;
 
    }
    return 0;
}
LL getCount(LL N){
    LL n=N;
    LL count=0;
    LL i;
    for (i = 1; i*i<= n ; i++){
        if (n % i == 0){
			if(flag==0){
             			arrays[i]=1;
                		count++; 
				if(i!=n/i){
					arrays[n/i]=1;
					count++;
				}
			}else{
				count++;
				if(arrays[i])
					sum++;
				if(i!=n/i){
					count++;
					if(arrays[n/i])
						sum++;
				}

			}
                
            }
            
       	}
    flag=1;
    return count;
}
//关于C++ map的使用遍历有兴趣可以看下实现源码