ACM算法题之杰哥和数字

★题目描述

杰哥特别喜欢和数字打交道，现在他有一个正整数X,他想知道有多少个满足要求的正整数D存在，要求是D是X的因子，并且D和X至少有一位相同。

★输入格式

只有一行，一个正整数X。

对于30%的数据，X<=100。

对于50%的数据，X<=200。

对于100%的数据，X<=1000000000。

★输出格式

只有一行，一个整数表示满足要求的数字D的个数。

★样例输入

10

★样例输出

2

★实例代码

#include<iostream>
#include<cmath>
#include<cstring>
#include <vector>

using namespace std;

vector<int> to_vector(int num) // 将num倒序存进向量vec
{
    vector<int> vec;
    while(num)
    {
        vec.push_back(num%10);
        num/=10;
    }
    return vec;
}

bool judge(int num,int factor,vector<int> &num_vec,vector<int> &factor_vec)  //判断num与factor是否存在相同数字
{
    bool flag = false;
    int num_len = num_vec.size();
    int factor_len = factor_vec.size();
    for (int i=0; i<num_len; i++)
    {
        for (int j=0; j<factor_len; j++)
        {
            if (num_vec[i]==factor_vec[j])
            {
                flag=true;
                break;
            }
        }
        if (flag==true)
            break;
    }
    return flag;
}


int main()
{
    int num,num_len,factor_len,res=0;
    vector<int> num_vec,factor_vec;
    cin>>num;
    num_vec = to_vector(num);
    for (int i=1; i<=sqrt(num); i++)
    {
        if (num%i==0)   //因子相同
        {
            if (i==sqrt(num))
            {
                factor_vec = to_vector(i);
                if(judge(num,i,num_vec,factor_vec))
                {
                    res+=1;
                }
                factor_vec.clear();  //清空存放因子的向量
            }
            else         //因子不同
            {
                factor_vec = to_vector(i);
                if(judge(num,i,num_vec,factor_vec))
                {
                    res+=1;
                }
                factor_vec.clear();  //清空存放因子的向量

                factor_vec = to_vector(num/i);
                if(judge(num,i,num_vec,factor_vec))
                {
                    res+=1;
                }

                factor_vec.clear();  //清空存放因子的向量
            }
        }
    }
    cout<<res<<endl;
}