TREELINE - VOI 2011 Hàng cây

Tác giả: flashmt

Ngôn ngữ: C++

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
#define maxn 100010
#define z 1000000000
using namespace std;

int n,a[maxn],re=2,np,p[maxn],d[maxn*2],f[maxn];

void prime()
{
    int i,j;
    fr(i,2,500)
      if (!d[i])
      {
          j=i*i;
          while (j<=200002)
          {
              d[j]=1;
              j+=i;  
          }
      } 
    fr(i,2,200002)
      if (!d[i]) p[++np]=i;
}

void calc(int n,int y)
{
    int i; 
    fr(i,1,np)
      if (p[i]<=n)
      {
        int x=p[i];
        while (x<=n)
        {
            f[i]+=(n/x)*y;
            if (p[i]<500) x*=p[i];  
            else break;
        }       
      } 
      else break;
}

int main()
{
    int i,j;
    cin >> n >> i;
    fr(i,1,n) scanf("%d",&a[i]);
    frr(i,n-1,1)
      if (a[i]<a[i+1]) re++;
      else break;
    cout << re << endl;
    n++;
    prime();
    calc(n*2,1);
    calc(n,-1);
    calc(n+1,-1);
    long long res=1;
    fr(i,1,np)
      if (f[i])
        fr(j,1,f[i])
          res=(res*p[i])%z;
    cout << res << endl;
    return 0;
}

Download