Problem - 7111 (hdu.edu.cn)
设f[i]为最少需要的次数，那么0<=f[i+1]-f[i]<=1,i后面可能是有多个数等于f[i]+1，这玩意就跟题目给的素数有关，假设ex[i]为i的最大质因子，那么f[j]=f[i]+1,j<i+e[i],然后这题就可以做了，用双指针扫一遍就可以
2021.ccpc 网络赛_Eter`nal的博客-CSDN博客_ccpc网络赛难度
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>
#include<iomanip>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
#include<set>
#include<ctime>
//HDU火车头
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(x) ((x)&(-x))
using namespace std;
const int mod=998244353;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);
}
ll pri[2000006],mp[2000006],cnt,ex[2000006];
bool ispri[2000006];
ull q[2000006],f[2000006];
void is_prime(ll n){memset(ispri,1,sizeof(ispri));cnt=0;ispri[0]=ispri[1]=0;mp[1]=1;for(int i=2;i<=n;i++){if(ispri[i]){pri[++cnt]=i;mp[i]=i;}for(int j=1;j<=cnt&&i*pri[j]<=n;j++){ispri[i*pri[j]]=0;mp[i*pri[j]]=pri[j];if(i%pri[j]==0) break;}}q[0]=1;for(int i=1;i<=2000000;i++)q[i]=q[i-1]*23333;
}
ll n,t,p;
int main(){scanf("%lld",&t);is_prime(2000000);while(t--){scanf("%lld%lld",&n,&p);ll maxx=0;for(int i=0;i<p;i++){ll x;scanf("%lld",&x);maxx=max(x,maxx);ex[x]=x;}ex[0]=maxx;f[1]=0;
for(int i=1,j=0;i<=n;++i){while(i-j>=ex[j]){++j;if(i==j) break;}if(i==j)break; //一旦 i==j 则证明能变成0的到头了，并且f[j]已经算过了，不能再多加了f[i]=f[j]+1;ex[i]=max(ex[mp[i]],ex[i/mp[i]]); //如果 i 本身就是质数，相当于可以 把 1 看成质因子，不影响结果,对于其他的总能用最大质因子去更新}ull ans=0;for(int i=1;i<=n;i++) ans+=f[i]*q[n-i];cout<<ans<<endl;for(int i=1;i<=n;i++) f[i]=0;for(int i=0;i<=maxx;i++) ex[i]=0;}return 0;
}
MEX maximizing 取模
统计y%x的个数，让k从0开始增加，如果k/x>=tx[k%x]就不能再增加了，因为假设x=2,k=6,tx[2]=3,k/x=3,3个2只可以来填0,2,4填不到6，所以k到6就要停止
#include <bits/stdc++.h>
#define ll long long
#define lowbit(i) (i)&(-i)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
#define all(x) (x).begin(),(x).end()
#define MOD(x) (((x)%mod+mod)%mod)
using namespace std;
const int mod=998244353;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);
}
ll q,x,tx[400005];
int main(){scanf("%lld%lld",&q,&x);ll k=0;while(q--){ll y;scanf("%lld",&y);tx[y%x]++;while(tx[k%x]>k/x) k++;printf("%lld\n",k);}return 0;
}
Problem - 7130 (hdu.edu.cn) Monopoly
取模要勤！
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(i) (i)&(-i)
#define all(x) (x).begin(),(x).end()
#define MOD(x) (((x)%mod+mod)%mod)
using namespace std;
const int mod=998244353;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);
}
ll t,n,m,a[100005],sum[100005],x;
map<ll,map<ll,ll>>mp;
int main(){scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&m);mp.clear();sum[0]=0;mp[0][0]=0;ll flag=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}if(sum[n]<0){flag=1;for(int i=1;i<=n;i++){a[i]=-a[i];sum[i]=sum[i-1]+a[i];}}for(int i=1;i<=n;i++){if(sum[n]>0){if(!mp[(sum[i]%sum[n]+sum[n])%sum[n]][sum[i]])mp[(sum[i]%sum[n]+sum[n])%sum[n]][sum[i]]=i;}else{if(!mp[sum[i]][sum[i]]&&sum[i]!=0){//cout<<sum[i]<<endl;mp[sum[i]][sum[i]]=i;}}}while(m--){ll x,ans=0;scanf("%lld",&x);if(flag) x=-x;if(sum[n]==0){if(mp[x][x]||x==0) ans=mp[x][x];else ans=-1;}else{
// ll y=abs(x/sum[n]);
// if(y*sum[n]<abs(x)) y++;
// y=y*sum[n];//cout<<(x+y)%sum[n]<<endl;ll y=(x%sum[n]+sum[n])%sum[n];if(mp[y].size()<=0) ans=-1;else{
// for(auto [a,b]:mp[(x+y)%sum[n]])
// cout<<a<<" sss "<<b<<endl;auto id=mp[y].upper_bound(x);if(id==mp[y].begin()) ans=-1;else{id--;//cout<<id->first<<" "<<id->second<<endl;ll z=(x-id->first)/sum[n];z=z*n;ans=z+id->second;}}}printf("%lld\n",ans);}}return 0;
}
1407C - Chocolate Bunny 交互
之前一道交互都没做过，今天被交互搞炸裂了，来熟悉一下交互的题
最多有2*n次，那么每个数最多花费两次询问就可以找到，可以发现q=pe[i]%pe[j],p=pe[j]%pe[i]，两者较小的那个就是原数，所以o(n)扫一遍就可以了
C. Chocolate Bunny（思维）_kuricip的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
#define lowbit(i) (i)&(-i)
#define all(x) (x).begin(),(x).end()
#define MOD(x) (((x)%mod+mod)%mod)
using namespace std;
const int mod=998244353;
const double inf=1e18;
const double eps=1e-8;
ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll getinv(ll a){return qpow(a,mod-2);}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);
}
ll n,a[100005];
int main(){scanf("%lld",&n);ll tmp=1;for(ll i=2;i<=n;i++){ll q,p;printf("? %lld %lld\n",tmp,i);fflush(stdout);scanf("%lld",&q);printf("? %lld %lld\n",i,tmp);fflush(stdout);scanf("%lld",&p);if(q>p) a[tmp]=q,tmp=i;else a[i]=p;}a[tmp]=n;printf("! ");for(int i=1;i<=n;i++) printf("%lld ",a[i]);printf("\n");return 0;
}
