首页 > ACM题库 > HDU-杭电 > HDU 4542-小明系列故事――未知剩余系-数论-[解题报告]HOJ
2015
02-17

HDU 4542-小明系列故事――未知剩余系-数论-[解题报告]HOJ

小明系列故事――未知剩余系

问题描述 :

  “今有物不知其数,三三数之有二,五五数之有三,七七数之有二,问物几何?”

  这个简单的谜题就是中国剩余定理的来历。

  在艰难地弄懂了这个定理之后,小明开始设计一些复杂的同余方程组X mod ai = bi 来调戏别人,结果是必然的,都失败了。

  可是在这个过程中,小明发现有时并不一定要把ai和bi告诉你。他只需要告诉你,ai在区间 [1, X] 范围内每个值取一次时,有K个ai使bi等于0,或有K个ai使bi不等于0,最小的X就可以求出来了。

  你来试试看吧!

输入:

输入第一行为T,表示有T组测试数据。
每组数据包含两个整数Type和K,表示小明给出的条件。Type为0表示“有K个ai使bi等于0”,为1表示“有K个ai使bi不等于0”。

[Technical Specification]

1. 1 <= T <= 477
2. 1 <= K <= 47777, Type = 0 | 1

输出:

输入第一行为T,表示有T组测试数据。
每组数据包含两个整数Type和K,表示小明给出的条件。Type为0表示“有K个ai使bi等于0”,为1表示“有K个ai使bi不等于0”。

[Technical Specification]

1. 1 <= T <= 477
2. 1 <= K <= 47777, Type = 0 | 1

样例输入:

3
0 3
1 3
0 10

样例输出:

Case 1: 4
Case 2: 5
Case 3: 48

在搜索方面仍然是渣的水平,高度拙计~不可救药。。。。之前算法还搞错了,弱爆。。。

第一问,可以参考codeforces 27E,实际上就是一个搜索,用到分解质因数法求约数个数的知识,然后搜索

第二问,搞一个不等式就得了,设g(x)为x的约数,则g(x)<=2*sqrt(x),所以从k+1开始往上枚举,直到i-2*sqrt(i)>K…

更正算法法,不断TLE,后来搞几个预处理,过了。。。附代码:

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

#define ss(a) scanf("%d",&a)
#define N 75
#define pb push_back
#define ll __int64
#define Max 4611686018427387904ULL

using namespace std;

int a[N],d[N];
ll e[N][N],mmax;
vector<int> b,c;

void deal(int n,int k,ll value)
{
    int i,j,x,y;
    if (n==1) 
    {
        if (value<=mmax) mmax=value;
        return;
    }
    for (i=1;i<c.size()&&c[i]<=n;i++)
        if (n%c[i]==0)
        {
            x=b[k];y=c[i]-1;
            if (d[x]<y) continue;
            if (mmax/value>=e[x][y]) deal(n/c[i],k+1,value*e[x][y]);
        }
}

void prime()
{
    int i,j;
    for (i=2;i<N;i++) 
        if (!a[i])
        {
            ll z=1;
            d[i]=0;
            e[i][0]=1;
            while (Max/z>=i) 
            {
                z*=i;
                e[i][++d[i]]=z;
            }
            b.pb(i);
            for (j=i*2;j<N;j+=i) a[j]=1;
        }   
}


int main()
{
    int i,j,k,n,T,cas=0;
    prime();
    ss(T);
    while (cas<T)
    {
        ss(k);ss(n);
        printf("Case %d: ",++cas);
        if (k==0)
        {
            mmax=Max;
            c.clear();
            for (i=1;i<=sqrt(n);i++)
                if (n%i==0) c.pb(i);
            int t=c.size()-1;
            for (i=t;i>=0;i--) 
                if (c[i]*c[i]!=n) c.pb(n/c[i]);
            deal(n,0,1);  
            if (mmax==Max) printf("INF\n");
            else printf("%I64d\n",mmax);
        }
        else
        {
            for (i=n+1;i-2*sqrt(i)<=n;i++)
            {
                int s=0;
                for (j=1;j<=sqrt(i);j++)
                    if (i%j==0)
                    { 
                        s++;
                        if (j*j!=i) s++;
                    }
                if (i-n==s)
                {
                    printf("%d\n",i);
                    break;
                }
            }
            if (i-2*sqrt(i)>n) printf("Illegal\n");
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/liverpippta/article/details/8826361