ZOJ 3622 Magic Number(击表)

ZOJ 3622 Magic Number(打表)
Magic Number

---

Time Limit: 2 Seconds      Memory Limit: 32768 KB

---

A positive number y is called magic number if for every positive integer x it satisfies that put y to the right of x, which will form a new integer z, z mod y = 0.

Input

The input has multiple cases, each case contains two positve integers m, n(1 <= m <= n <= 2^31-1), proceed to the end of file.

Output

For each case, output the total number of magic numbers between m and n(m, n inclusively).

Sample Input

1 1
1 10

Sample Output

1
4

题意：有一类数，该数放在任何数的右面后形成的新数对原数取余为0。例如2，无论2放在什么数的右面，形成的数总是偶数，因此对2取余都为0.给出m和n求两者之间有多少个这样的数。
题解：这些数必须是1,10，100,1000,10000.。。。的因子。直接 求出这些数的因子 再遍历即可。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

vector<ll>vec;

void init() {
    vec.push_back(1);
    ll fa=10;
    int k=2;
    while(k<=11) {
        ll x=fa;
        ll y=fa/10;
        vec.push_back(x);
        for(ll i=2; i*i<=x; i++) {
            if(x%i==0) {
                if(i>y)vec.push_back(i);
                ll j=x/i;
                if(j==i)continue;
                if(j>y)vec.push_back(j);
            }
        }
        fa*=10;
        k++;
    }
}

void debug() {
    sort(vec.begin(),vec.end());
    for(int i=0; i<vec.size(); i++) {
        printf("%lld ",vec[i]);
    }
    cout<<endl;
}
int main() {
    //freopen("test.in","r",stdin);
    init();
    //debug();
    ll n,m;
    while(cin>>n>>m) {
        int ans=0;
        for(int i=0; i<vec.size(); i++) {
            if(vec[i]>=n&&vec[i]<=m)ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}