URAL 2047 Maths 打表 递推

时间：2025-04-23 18:05:31

Maths
Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87157#problem/B

Description

Android Vasya attends Maths classes. His group started to study the number theory recently. The teacher gave them several tasks as a homework. One of them is as follows.
There is an integer n. The problem is to find a sequence of integers a1, …, an such that for any k from 2 to n the sum a1 + … + ak has exactly ak different positive divisors. Help Vasya to cope with this task.

Input

The only line contains an integer n (2 ≤ n ≤ 100 000).

Output

If there is no such sequence output “Impossible”. Otherwise output space-separated integers a1, …, an (1 ≤ ai ≤ 300).

Sample Input

3

Sample Output

1 3 4

HINT

题意

让你构造n个数，要求a1+……+ak的和的因子数恰好为ak

题解：

假设我们已经构造出了ak,且前缀和sum已知，那么ak-1=sum-ak，这个是显然的结论

于是我们直接打表打出来100000位就好了，然后把sum求出来，然后前面直接递推就好了

代码：

打表程序：

#pragma comment(linker, "/STACK:102400000,102400000")

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 2000001

#define mod 1000000007

#define eps 1e-9

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

int cnt[*];

vector<int> Q;

int flag=;

int n;

void dfs(int N,int sum,int z)

{

    if(flag)

        return;

    if(sum+z>*)

        return;

    if(N>&&cnt[sum]!=z)

        return;

    if(N==n)

    {

        printf("%d",Q[]);

        for(int i=;i<Q.size();i++)

            printf(" %d",Q[i]);

        printf("\n");

        cout<<sum<<endl;

        flag=;

        return;

    }

    for(int i=;i<=;i++)

    {

        Q.push_back(i);

        dfs(N+,sum+i,i);

        Q.erase(Q.end()-);

    }

}

int main()

{

    freopen("1.out","w",stdout);

    for(int i=;i<=*;i++)

    {

        for(int j=i;j<*;j+=i)

        {

            cnt[j]++;

        }

    }

    n=read();

    Q.clear();

    flag=;

    for(int i=;i<=;i++)

    {

        Q.push_back(i);

        dfs(,i,i);

        Q.erase(Q.end()-);

    }

    if(flag==)

        printf("Impossible\n");

}

AC程序：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 20001

#define mod 1000000007

#define eps 1e-9

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

const int N=;

int cnt[N];

int a[N],sum=;

vector<int> Q;

int flag=;

int n;

int tot;

int main()

{

    for(int i=;i<N;i++)

    {

        for(int j=i;j<N;j+=i)

            cnt[j]++;

    }

    for(int p=,i=;i>;p-=cnt[p],i--)

    {

        a[i]=cnt[p];

        sum+=a[i];

    }

    n=read();

    for(int i=;i<n;i++) printf("%d ",a[i]);

    printf("%d\n",a[n]);

}

相关文章