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?a₁, …,?a_n?such that for any?k?from 2 to?n?the sum?a₁?+ … +?a_k?has exactly?a_k?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?a₁, …,?a_n?(1 ≤?a_i?≤ 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=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //**************************************************************************************int cnt[300*200010]; vector<int> Q; int flag=0; int n; void dfs(int N,int sum,int z) {if(flag)return;if(sum+z>300*100000)return;if(N>1&&cnt[sum]!=z)return;if(N==n){printf("%d",Q[0]);for(int i=1;i<Q.size();i++)printf(" %d",Q[i]);printf("\n");cout<<sum<<endl;flag=1;return;}for(int i=1;i<=300;i++){Q.push_back(i);dfs(N+1,sum+i,i);Q.erase(Q.end()-1);}} int main() {freopen("1.out","w",stdout);for(int i=1;i<=300*100010;i++){for(int j=i;j<300*100010;j+=i){cnt[j]++;}}n=read();Q.clear();flag=0;for(int i=1;i<=300;i++){Q.push_back(i);dfs(1,i,i);Q.erase(Q.end()-1);}if(flag==0)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=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //************************************************************************************** const int N=2000000; int cnt[N]; int a[N],sum=0; vector<int> Q; int flag=0; int n; int tot; int main() {for(int i=1;i<N;i++){for(int j=i;j<N;j+=i)cnt[j]++;}for(int p=1586335,i=100000;i>0;p-=cnt[p],i--){a[i]=cnt[p];sum+=a[i];}n=read();for(int i=1;i<n;i++) printf("%d ",a[i]);printf("%d\n",a[n]); }

?

轉載于:https://www.cnblogs.com/qscqesze/p/4718887.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的URAL 2047 Maths 打表 递推的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。