1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=51;
 5 ll n,m,a[N],lj[N],ans,sum,len,tmp;
 6  
 7 inline ll re_ad() {
 8     char ch=getchar(); ll x=0,f=1;
 9     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
10     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
11     return x*f;
12 }
13  
14 inline ll gcd(ll x,ll y) { return !y?x:gcd(y,x%y); }
15  
16 void dfs(ll d) {
17 //  printf("%lld\n",d);
18     if(d>=n+1) {
19 //      printf("%lld %lld\n",len,sum);
20         tmp=((len&1)?-1:1)*sum;
21         ans+=m/tmp;
22         return ;
23     }
24     dfs(d+1);
25     if(a[d]>m) return ;
26     ll G=gcd(sum,a[d]);
27 //  printf("gcd: %lld %lld %lld\n",sum,a[d],G);
28     if(sum/G*a[d]>m) return ;
29     sum=sum/G*a[d],lj[d]=1,++len;
30     dfs(d+1);
31     sum=sum/a[d]*G,lj[d]=0,--len;
32 }
33  
34 int main()
35 {
36     m=re_ad(),n=re_ad();
37     for(ll i=1;i<=n;++i) a[i]=re_ad();
38     if(n==0) { printf("%lld\n",m); return 0; }
39     sum=1,dfs(1);
40     printf("%lld\n",ans);
41 //  system("pause");
42     return 0;
43 }

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=4e5+11,Tree_Sz=1e6+6e5+11;
 5 ll n,nn,k,a[N],b[N],seg[N];
 6  
 7 inline ll re_ad() {
 8     char ch=getchar(); ll x=0,f=1;
 9     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
10     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
11     return x*f;
12 }
13  
14 namespace ST {
15     ll val[2][Tree_Sz];
16     inline void Init() {
17         for(int i=0;i<=(n<<3)+(n<<1);++i) val[0][i]=val[1][i]=0;
18     }
19     inline void Pushup(ll d,ll op) {
20         val[op][d]=val[op][d<<1]+val[op][d<<1|1];
21     }
22     void modify(ll d,ll l,ll r,ll x,ll z,ll op) {
23         if(l==r) {
24             val[op][d]+=z;
25             return ;
26         }
27         ll mid=(l+r)>>1;
28         if(x<=mid) modify(d<<1,l,mid,x,z,op);
29         else modify(d<<1|1,mid+1,r,x,z,op);
30         Pushup(d,op);
31     }
32     inline void Modify(ll x,ll z,ll op) {
33         modify(1,1,n*2,x+n,z,op);
34     }
35     ll query(ll d,ll l,ll r,ll x,ll y,ll op) {
36         if(x<=l && r<=y) {
37             return val[op][d];
38         }
39         ll mid=(l+r)>>1,res=0;
40         if(x<=mid) res+=query(d<<1,l,mid,x,y,op);
41         if(y>=mid+1) res+=query(d<<1|1,mid+1,r,x,y,op);
42         return res;
43     }
44     inline ll Query(ll x,ll op) {
45         return query(1,1,n*2,x+n,n*2,op);
46     }
47 }
48  
49 inline bool check(ll d) {
50     ST::Init();
51     ll res=0,lj=0;
52     for(ll i=1;i<=n;++i) seg[i]=(a[i]>d)?1:-1;
53     ST::Modify(seg[1],1,0);
54     res+=(seg[1]==1)?1:0;
55     for(ll i=2,j=1;i<=n;++i,j^=1) {
56         lj-=seg[i];
57         ST::Modify(seg[i]+lj,1,j);
58 //      printf("awa\n");
59         res+=ST::Query(lj+1,j);
60     }
61 //  printf("check: %lld %lld\n",d,res);
62     if(res<k) return true;
63     return false;
64 }
65  
66 inline ll Binary_Find() {
67     ll l=1,r=n,ans=0;
68     while(l<=r) {
69         ll mid=(l+r)>>1;
70 //      printf("mid: %lld %lld %lld\n",l,r,mid);
71         if(check(b[mid])) r=mid-1,ans=mid;
72         else l=mid+1;
73     }
74     return b[ans];
75 }
76  
77 int main()
78 {
79     n=re_ad(),k=re_ad();
80     for(ll i=1;i<=n;++i) b[i]=a[i]=re_ad();
81     sort(b+1,b+n+1);
82     for(ll i=n;i>=1;i-=2) nn+=i;
83 //  printf("%lld\n",nn);
84     printf("%lld\n",Binary_Find());
85 //  for(ll i=1;i<=nn;++i) printf("%lld ",check(i)); puts("");
86 //  system("pause");
87     return 0;
88 }

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=2e6+11,mod=1e9+7;
 5 ll n,a[N],A,B,C,b[N],num,c[N];
 6  
 7 namespace BIT1 {
 8     ll t[N];
 9     inline ll lowbit(ll d) { return d&(-d); }
10     inline void insert(ll d,ll x) { for(;d<=num+1;d+=lowbit(d)) t[d]+=x; }
11     inline ll query(ll d) { ll res=0; for(;d>0;d-=lowbit(d)) res+=t[d]; return res; }
12 }
13  
14 namespace BIT2 {
15     ll t[N];
16     inline ll lowbit(ll d) { return d&(-d); }
17     inline void insert(ll d,ll x) { for(;d<=num+1;d+=lowbit(d)) t[d]+=x; }
18     inline ll query(ll d) { ll res=0; for(;d>0;d-=lowbit(d)) res+=t[d]; return res; }
19 }
20  
21 int main()
22 {
23     scanf("%lld%lld%lld%lld%lld",&n,&a[1],&A,&B,&C);
24     b[1]=a[1];
25     for(ll i=2;i<=n;++i) b[i]=a[i]=((a[i-1]*A)%C+B)%C;
26 //  printf("a: "); for(ll i=1;i<=n;++i) printf("%lld ",a[i]); puts("");
27     sort(b+1,b+n+1);
28     num=unique(b+1,b+n+1)-b-1;
29 //  printf("b: "); for(ll i=1;i<=n;++i) printf("%lld ",b[i]); puts("");
30     for(ll i=1;i<=n;++i) c[i]=lower_bound(b+1,b+num+1,a[i])-b;
31 //  printf("c: "); for(ll i=1;i<=n;++i) printf("%lld ",c[i]); puts("");
32     ll ans=0;
33     for(ll i=1;i<=n;++i) {
34         ll t1=BIT1::query(c[i]-1+1)%mod;
35 //      printf("%lld ",t1);
36         (t1*=a[i]*(n-i+1)%mod)%=mod;
37 //      printf("%lld ",t1);
38         ll t2=(BIT2::query(num+1)-BIT2::query(c[i]+1))%mod;
39 //      printf("%lld ",t2);
40         (t2*=(n-i+1))%=mod;
41 //      printf("%lld ",t2);
42         (ans+=t1)%=mod;
43 //      printf("%lld ",ans);
44         (ans+=t2)%=mod;
45 //      printf("%lld\n",ans);
46         BIT1::insert(c[i]+1,i); //printf("insert1: %lld %lld\n",a[i]+1,i);
47         BIT2::insert(c[i]+1,(i*a[i])%mod);
48 //      printf("test: %lld %lld %lld\n",BIT1::query(4),BIT1::query(5),BIT1::query(6));
49     }
50     for(ll i=1;i<=n;++i) (ans+=(i*(n-i+1)%mod)*a[i]%mod)%=mod;
51     printf("%lld\n",ans);
52 //  if(n>1e5) printf("%lld\n",n);
53     return 0;
54 }