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=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(" "); 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 "); }
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 ",a[n]); }