Integer Product 解题分析

Integer Product 解题分析

问题描述:

给出\( N \) 个数字\(A_i \),形式可能是整数或小数,统计有多少对 \( (A_i,A_j) ( i<j ) \)的乘积\( A_i \cdot A_j \)为整数。

数据限制:
\( 0 < N \leq 200000 \)
\( 0 < A_i <10^{4} \)
\( A_i \) 若为小数则小数点后最多有9位数字

分析:

小数点后可能有9位,那么两个小数点后都是9位的数字相乘则精度会超过double允许的类型,所以可以将小数转化为分数,编写一个有理数类。对于小数\(a.b = a + 0.b \),若小数点后的\(b\)部分的长度为\( L \) 则\(a.b\)可写为分数形式\(\frac{a \cdot 10^L+b}{10^L}\),再编写判断两个分数相乘是否为整数就可以,遍历所有\( A_i\)以及\( i<j \)的\( A_j \) 统计数量即可。


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using ll = long long ;
#define MAXN 200009

long long gcd(ll a ,ll b)
{
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}

class Rat
{
    public:
        Rat(){}
        ll num,den;
        Rat(ll nn,ll dd)
        {
           ll G = gcd(nn,dd);
           num = nn/G; 
           den = dd/G;
        }

        int MultiIsInt(const Rat o )
        {
            return (o.num % den ==0) && (num%o.den==0);
        }
    
        void output() 
        { 
            printf("%lld/%lld\n",num,den); 
        } 

        bool operator<(const Rat o)
        {
            return num*1.0/den < o.num*1.0/o.den;
        }
}a[MAXN]; 
        
#define MAXL 29 

int main(void) 
{ 
    char theNumber[MAXL]; 
    int N,i,j;
    scanf("%d",&N);

    for (i=0;i<N;i++){
        scanf("%s",theNumber);
        char* ret = strchr(theNumber,'.');
        if (ret==NULL){
            a[i] = Rat(atoi(theNumber),1); 
        } else {
            int lenOfDen = strlen(&theNumber[ret-&theNumber[0]+1]);
            ll den = pow(10,lenOfDen); 
            ll num = atoi(theNumber)*den
            +atoi(&theNumber[ret-&theNumber[0]+1]);
            a[i] = Rat(num,den);
        }
    }

    int s=0;
    for(i=0;i<N;i++)
    {
        for(j=i+1;j<N;j++)
        {
            if(a[i].MultiIsInt(a[j])==1)
            {
                s+=1;
            }
        }
    }
    printf("%d\n",s);
    return 0;
}


然而这个程序给出了 AC*5,TLE*5的结果。说明此题这种\( O(N^2) \)的效率并不合格。

针对本题,转化成有理数运算的思路是正确的,但不需要使用有理数的运算,因为从小数化为分数,分数的分母都是从\(10^L\)开始,并可能被约分,最后分母只剩\(2^a 5^b \)的形式,也就是说如果要将一个数字的分母\( 2^a \cdot 5^b \)约去,只需要看这个数字的分子与另一个数字的分子之积是否含有\( 2^a \cdot 5^b \)的因子,其它的因子都不会有影响。例如\( 7.5 = \frac{75}{10} = \frac{15}{2}\),它在本题中与\( \frac{5}{2} \)起到的作用是相同的,因为\( 15=3 \times 5 \),但是因子\( 3 \)在分子上无论如何也不会将分母 \( 2^a 5^b \) 约去任何一部分,只有因子\(5\)有作用。

这样,在本题中,我们将每个数字用\( (a,b) \) 描述,对应于\(2^a \cdot 5^b \)。若两数相乘为整数,则两数 \(2^a \cdot 5^b \) 与 \(2^c \cdot 5^d \)的乘积是 \(2^{a+c} \cdot 5^{b+d} \),即\((a+c,b+d) \) ,若有\( a+c \geq 0 \text{ and } b+d \geq 0 \),则两数之积为整数。

由于小数最多有9位,即最小的数字是\( 0.000000001 \),即\( 2^{-9}\cdot 5^{-9} \) ,最大可能为\( 10000 \) ,即\( 2^{4}\cdot 5^{4} \) 只需要一个二维数组,将相应a与b的数字数量存入数组,只需要遍历整个数组即可计算结果。或者使用map<pair<int,int>,int>结构保存,map的键是2的幂a与5的幂b组成的pair (a,b),map对应的值为这个(a,b)所对应的数字个数。二重遍历map可以计算得到结果。Accepted的程序代码如下所示

 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <utility>

using ll = long long ;
#define MAXN 200009
#define MAXL 29 
std::map<std::pair<int,int>, int> bucket;

class Rat
{
    private:
        int cofp2,cofp5;
    public:
        Rat(){}
        Rat(ll nn,ll dd)
        {
           ll tn = nn;
           ll td = dd;
           cofp2 = 0;
           while( tn%2==0){
               cofp2++;
               tn/=2;
           } 
           while(td%2==0){
               cofp2--;
               td/=2;
           }
           cofp5=0;
           while(tn%5==0){
               cofp5++;
               tn/=5;
           }
           while(td%5==0){
               cofp5--;
               td/=5;
           }
        }
        void output() 
        { 
            printf("2^{%d}*5^{%d}\n",cofp2,cofp5); 
        } 
        int getcofp2()
        {
            return cofp2;
        }
        int getcofp5()
        {
            return cofp5;
        }
}; 
        

int main(void) 
{ 
    char theNumber[MAXL]; 
    int N,i,j;
    scanf("%d",&N);
    Rat *a ;

    for (i=0;i<N;i++){
        scanf("%s",theNumber);
        char* ret = strchr(theNumber,'.');
        if (ret==NULL){
            a = new Rat(atoi(theNumber),1); 
        } else {
            int lenOfDen = strlen(&theNumber[ret-&theNumber[0]+1]);
            ll den = pow(10,lenOfDen); 
            ll num = atoi(theNumber)*den
            +atoi(&theNumber[ret-&theNumber[0]+1]);
            a = new Rat(num,den);
        }
        bucket[std::make_pair(a->getcofp2(),a->getcofp5())] ++;
    }

    ll s=0;
    for (auto it:bucket) {
        int x1 = it.first.first;
        int y1 = it.first.second;
        int r1 = it.second;
        for (auto it2:bucket) {
            int x2 = it2.first.first;
            int y2 = it2.first.second;
            int r2 = it2.second;

            if(x1+x2>=0 && y1+y2>=0)
            {
                if(it<it2){
                    s+=((ll)r1)*r2;
                } else if (it==it2) {
                    s+=((ll)r1*(r1-1))/2;
                }
            }
        }
    }

    printf("%lld\n",s);

    return 0;
}
 
 
N = int(input())

bucket = dict()

def keyGen(num,den=1):
	c2 = 0
	c5 = 0
	while num%2==0:
		c2+=1
		num/=2
	while den%2==0:
		c2-=1
		den/=2
	while num%5==0:
		c5+=1
		num/=5
	while den%5==0:
		c5-=1
		den/=5
	return (c2,c5)

def addItem(d,key1):
	if key1 in d:
		d[key1]+=1
	else:
		d[key1]=1

for _ in range(N):
	theNumber = input()
	dpoint = theNumber.find('.')
	if(dpoint>-1):
		a=int(theNumber[:dpoint])
		lenOfDen = len(theNumber[1+dpoint:])
		b=int(theNumber[1+dpoint:])
		num = a*10**lenOfDen+b
		den = 10**lenOfDen
		addItem(bucket,keyGen(num,den))
	else:
		addItem(bucket,keyGen(int(theNumber)))

s=0
for it in bucket:
	x1 = it[0]
	y1 = it[1]
	r1 = bucket[it]
	for it2 in bucket:
		x2 = it2[0]
		y2 = it2[1]
		r2 = bucket[it2]
		if x1+x2>=0 and y1+y2>=0:
			if(it<it2):
				s+=r1*r2
			elif(it==it2):
				s+=(r1*(r1-1))//2

print(s)
 
 
using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int N;
            Dictionary<Tuple<int, int>, int> bucket = new Dictionary<Tuple<int, int>, int>();
            N = Convert.ToInt32(Console.ReadLine());
            numNode a;
            for (int i = 0; i < N; i++)
            {
                var theNumber = Console.ReadLine();
                var pos = theNumber.IndexOf('.');
                if (pos == -1)
                {
                    a = new numNode(theNumber);
                }
                else
                {
                    var intpart = Convert.ToInt64(theNumber.Substring(0, pos));
                    var powOfDen = Convert.ToInt64(Math.Pow(10, Convert.ToDouble(theNumber.Length - pos - 1)));
                    var decipart = Convert.ToInt64(theNumber.Substring(pos + 1));
                    a = new numNode(intpart * powOfDen + decipart, powOfDen);
                }
                if (bucket.ContainsKey(a.GetTuple()))
                {
                    bucket[a.GetTuple()] += 1;
                }
                else
                {
                    bucket[a.GetTuple()] = 1;
                }
            }

            Int64 s = 0;
            foreach (var it in bucket.Keys)
            {
                var x1 = it.Item1;
                var y1 = it.Item2;
                var r1 = bucket[it];
                foreach (var it2 in bucket.Keys)
                {
                    var x2 = it2.Item1;
                    var y2 = it2.Item2;
                    var r2 = bucket[it2];
                    if (x1 + x2 >= 0 && y1 + y2 >= 0)
                    {
                        if (lessThan(it , it2))
                        {
                            s += r1 * r2;
                        }
                        else if (it == it2)
                        {
                            s += (r1 * (r1 - 1)) / 2;
                        }
                    }
                }
            }
            Console.WriteLine(s);
        }
        private static bool lessThan(Tuple<int,int> a,Tuple<int,int> b)
        {
            if(a.Item1==b.Item1)
            {
                return a.Item2 < b.Item2;
            }
            else
            {
                return a.Item1 < b.Item1;
            }
        }
       
    }
    
    
    
    class numNode
    {
        private int c2 { get; set; }
        private int c5 { get; set; }

        public numNode() { }

        public numNode(Int64 num, Int64 den)
        {
            c2 = 0;
            while (num % 2 == 0)
            {
                c2++;
                num /= 2;
            }
            while (den % 2 == 0)
            {
                c2--;
                den /= 2;
            }
            c5 = 0;
            while (num % 5 == 0)
            {
                c5++;
                num /= 5;
            }
            while (den % 5 == 0)
            {
                c5--;
                den /= 5;
            }
        }
        public numNode(string v)
        {
            int num = Convert.ToInt32(v);
            c2 = 0;
            while (num % 2 == 0)
            {
                c2++;
                num /= 2;
            }
            c5 = 0;
            while (num % 5 == 0)
            {
                c5++;
                num /= 5;
            }
        }
        public Tuple<int, int> GetTuple()
        {
            return new Tuple<int, int>(c2, c5);
        }

    }
}
 

发表评论

电子邮件地址不会被公开。 必填项已用*标注