pinuocao

2645

T-God韩枫

baizhiren
cloudsRise
CJR__LKP

ztxcsl
ZhaoYvDr

Present.
hh想拿牌子

FeoBay
coolcoder
Cold_heartless
imnoob

#include<bits/stdc++.h>
using namespace std;
int x;
int primes[100005],cnt;
bool st[100005];
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]*i<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
scanf("%d",&x);
init(x+4);
if(x==2||x==1) printf("1\n");
else printf("2\n");
for(int i=2;i<=x+1;i++)
if(st[i]) printf("2 ");
else printf("1 ");
return 0;
}



#include<bits/stdc++.h>
using namespace std;
int x;
int primes[1000010],cnt;
bool st[1000010];
void init(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]*i<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
init(1000009);
while(scanf("%d",&x))
{
if(!x) break;
for(int i=1;;i++)
{
int a=primes[i];
int b=x-a;
if(!st[b])
{
printf("%d = %d + %d\n",x,a,b);
break;
}
}
}
return 0;
}



pinuocao
6个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=20;
const ll mod=(ll)(1e9+7);
ll bit[maxn],tp[maxn];
struct node
{
ll cnt;
ll sum;
ll sqsum;
node(ll _cnt=0,ll _sum=0,ll _sqsum=0):cnt(_cnt),sum(_sum),sqsum(_sqsum){}
}F[maxn][maxn][maxn];
node dfs(int pos,int sum,int ori,bool lead,bool limit)
{
node ret, tmp;
if(!pos) return node((sum&&ori), 0, 0);
if(!limit && !lead && F[pos][sum][ori].cnt != -1) return F[pos][sum][ori];
int endi=limit?bit[pos]:9;
tmp=node(0, 0, 0);
for (int i = 0; i <= endi; i ++) {
if(i == 7) continue;
ret = dfs(pos-1, (sum+i)%7, (ori*10+i)%7, lead&&!i, limit&&(i==endi));
tmp.cnt = (tmp.cnt + ret.cnt) % mod;
tmp.sum = (tmp.sum + ret.sum + ret.cnt * i % mod * tp[pos-1] % mod) % mod;
tmp.sqsum = (tmp.sqsum + ret.sqsum + 2 * ret.sum % mod * i % mod * tp[pos-1] % mod) % mod;
tmp.sqsum = (tmp.sqsum + i * i * tp[pos-1] % mod * tp[pos-1] % mod * ret.cnt % mod) % mod;
}
return (!limit&&!lead) ? F[pos][sum][ori] = tmp: tmp;
}
ll solve(ll x)
{
bit[0]=0;
while(x){
bit[++bit[0]]=x%10;
x/=10;
}
return dfs(bit[0],0,0,1,1).sqsum;
}
int main()
{
memset(F,-1,sizeof(F));
tp[0] = 1;
for (int i=1; i<=19; ++i) tp[i]=tp[i-1]*10 % mod;
int T;
scanf("%d", &T);
while (T--) {
long long L, R;
scanf("%lld%lld", &L, &R);
printf("%lld\n", (solve(R) - solve(L-1) + mod) % mod);
}
return 0;
}


pinuocao
6个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
const int N = 500010;
int n,ww;
int w[1005],v[1005],dp[1005];
ll cnt[1005];
int main()
{
scanf("%d%d",&n,&ww);
for(int i=0;i<=ww;i++) cnt[i]=1;
for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
for(int i=1;i<=n;i++)
for(int j=ww;j>=w[i];j--)
{
if(dp[j]<dp[j-w[i]]+v[i])
cnt[j]=cnt[j-w[i]];
else if(dp[j]==dp[j-w[i]]+v[i])
{
cnt[j]+=cnt[j-w[i]];
cnt[j]%=mod;
}
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
printf("%lld",cnt[ww]);
return 0;
}


pinuocao
6个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
const int N = 500010;
int n;
ll q[N], w[N];
ll merge_sort(int l, int r)
{
if (l == r) return 0;
int mid = l + r >> 1;
ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if (q[i] <= q[j]) w[k ++ ] = q[i ++ ];
else
{
res += mid - i + 1;
w[k ++ ] = q[j ++ ];
}
while (i <= mid) w[k ++ ] = q[i ++ ];
while (j <= r) w[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = w[j];
return res;
}
int main()
{
while (scanf("%d", &n), n)
{
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
printf("%lld\n", merge_sort(0, n - 1));
}
return 0;
}


pinuocao
6个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
priority_queue<int, vector<int>, greater<int>> sml;
priority_queue<int> big;
int idx, n, mid,cnt=1;
scanf("%d%d%d",&idx, &n, &mid);
printf("%d %d\n%d ", idx,(n+1)/2,mid);
for (int i = 2, x; i <= n; i++)
{
scanf("%d", &x);
if (x > mid) sml.push(x);
else big.push(x);
if (i & 1)
{
while (sml.size() != big.size())
if (big.size() > sml.size())
{
sml.push(mid);
mid = big.top();
big.pop();
}
else
{
big.push(mid);
mid = sml.top();
sml.pop();
}
cnt++;
if(cnt==11) {printf("\n");cnt=1;}
printf("%d ", mid);
}
}
printf("\n");
}
return 0;
}


pinuocao
7个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int l,r,n,a[35];
int dp[35][320];
int dfs(int pos,int sum,bool limit)
{
if(!pos) return sum%n==0;
if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum];
int ans=0,end=limit?a[pos]:9;
for(int i=0;i<=end;i++)
ans+=dfs(pos-1,sum+i,limit&&i==end);
if(!limit) dp[pos][sum]=ans;
return ans;
}
int solve(int x)
{
memset(dp,-1,sizeof(dp));
int pos=0;
while(x)
{
a[++pos]=x%10;
x/=10;
}
return dfs(pos,0,1);
}
int main()
{
while(scanf("%d%d%d",&l,&r,&n)!=EOF)
printf("%d\n",solve(r)-solve(l-1));
return 0;
}


pinuocao
7个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int a[20];
ll dp[20][20];
int dfs(int pos,bool lead0,int pre,bool limit)
{
if(!pos) return 1;
int ans=0,end=limit?a[pos]:9;
for(int i=0;i<=end;i++)
{
}
return ans;
}
int solve(int x)
{
int pos=0;
while(x)
{
a[++pos]=x%10;
x/=10;
}
return dfs(pos,0,0,1);
}
int main()
{
memset(dp,-1,sizeof(dp));
int l,r;
scanf("%d%d",&l,&r);
printf("%d",solve(r)-solve(l-1));
return 0;
}


pinuocao
7个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int l,r,a[35];
int dp[35][11];
int dfs(int pos,int pre,bool limit)
{
if(!pos) return 1;
if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];
int ans=0,end=limit?a[pos]:9;
for(int i=0;i<=end;i++)
if(i<pre) continue;
else ans+=dfs(pos-1,i,limit&&i==end);
if(!limit) dp[pos][pre]=ans;
return ans;
}
int solve(int x)
{
memset(dp,-1,sizeof(dp));
int pos=0;
while(x)
{
a[++pos]=x%10;
x/=10;
}
return dfs(pos,0,1);
}
int main()
{
while(scanf("%d%d",&l,&r)!=EOF)
printf("%d\n",solve(r)-solve(l-1));
return 0;
}


pinuocao
7个月前
#include<bits/stdc++.h>
using namespace std;
//#define mod 998244353
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
typedef long long ll;
int l,r,k,b,a[35];
int dp[35][35];
int dfs(int pos,int cnt,bool limit)
{
if(!pos) return cnt==k;
if(!limit&&dp[pos][cnt]!=-1) return dp[pos][cnt];
int ans=0,end=limit?min(a[pos],1):1;
for(int i=0;i<=end;i++)
if(cnt+i>k) continue;
else ans+=dfs(pos-1,cnt+i,limit&&i==a[pos]);
if(!limit) dp[pos][cnt]=ans;
return ans;
}
int solve(int x)
{
memset(dp,-1,sizeof(dp));
int pos=0;
while(x)
{
a[++pos]=x%b;
x/=b;
}
return dfs(pos,0,1);
}
int main()
{
scanf("%d%d%d%d",&l,&r,&k,&b);
printf("%d",solve(r)-solve(l-1));
return 0;
}

/*
763 8698
7
3
*/