首页 > 代码库 > [题解]BZOJ1004 序列函数

[题解]BZOJ1004 序列函数

原题找不到了,应该是usaco之类的题目吧。给一个可以交题的链接:http://www.cqoi.net:2012/problem.php?id=1004

思路:将素数一个一个往里乘,保证扫描的顺序是从小到大的就可以了。思路跟usaco training的丑数有点像,算是那道题的简单版吧。

 

我的实现:

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 #define MAXN 10020 7 #define INF 100000000000000000 8 #define llt long long 9 llt N,n,ans;10 llt c[5],Num[5],mul[MAXN];11 inline void Get_llt(llt &Ret)12 {13     char ch;14     bool flag=false;15     for(;ch=getchar(),ch<0||ch>9;)16         if(ch==-)17             flag=true;18     for(Ret=ch-0;ch=getchar(),ch>=0&&ch<=9;Ret=Ret*10+ch-0);19     flag&&(Ret=-Ret);20 }21 int main()22 {23     llt i,j;24     Get_llt(N);25     while(N--)26     {27         Get_llt(c[1]);Get_llt(c[2]);Get_llt(c[3]);28         Get_llt(n);29         mul[0]=1;30         memset(Num,0,sizeof(Num));31         for(i=0;i<n;i++)32         {33             ans=INF;34             for(j=1;j<=3;j++)35             {36                 while(c[j]*mul[Num[j]]<=mul[i])37                     Num[j]++;38                 ans=min(ans,c[j]*mul[Num[j]]);39             }40             mul[i+1]=ans;41         }42         printf("%lld\n",mul[i]);43     }44     return 0;45 }
View Code