题目都超链接了，可以直接点开。
P1143 进制转换
十进制与 $n$ 进制的互相转换，板子题，不多说。
string c="0123456789ABCDEF";
void f(int x,int m)
{
if(x/m)
{
f(x/m,m);
}
cout<<c[x%m];
}
int fu(string x,int m)
{
reverse(x.begin(),x.end());
int sum=0,cnt=1;
for(int i=0;i<x.size();i++)
{
sum+=cnt*(x[i]-(x[i]>='0'&&x[i]<='9'?48:55));
cnt*=m;
}
return sum;
}
void solve()
{
int n,m;
string s;
cin>>n>>s>>m;
f(fu(s,n),m);
}P1469 找筷子
清楚两个异或相关的概念。
相同数异或，结果为 $0$。
$0$ 与一个数异或，结果等于那一个数。
恰巧这题 $n$ 范围较大，空间较小，用此概念。
答案即为所有数异或。
void solve()
{
int x=0,y,n;
cin>>n;
while(n--)
{
cin>>y;
x^=y;
}
cout<<x<<endl;
}P1100 高低位交换
位运算。
a<<x 为 $a$ 向左移动 $x$ 位。
a>>x 为 $a$ 向右移动 $x$ 位。
$2^{32}$ 爆 int，但是用 unsigned int 就够了。
样例是一生一世我爱你可还行，被酸了。
void solve()
{
unsigned int n;
cin>>n;
cout<<(n<<16)+(n>>16)<<endl;
}P1017 [NOIP2000 提高组] 进制转换
负数进制与十进制转换。
可以去看我的
题解，同步发表于洛谷博客。
这题就是 AT4239 的双倍经验，看我的博客吧，不说了。
int a[100005];
string c="0123456789ABCDEFGHIJ";
void solve()
{
ll n,r;
cin>>n>>r;
int x=-1;
if(n==0)
{
printf("0=0(base%lld)",r);
return;
}
printf("%lld=",n);
while(n!=0)
{
a[++x]=n%(r);
n/=(r);
if(a[x]<0)
{
n++;
a[x]-=r;
}
}
reverse(a,a+x+1);
for(int i=0;i<=x;i++)
{
cout<<c[a[i]];
}
printf("(base%lld)",r);
}P1866 编号
排列组合。
注意，前面兔子选的数，后面不能选，所以要减一下。
注意答案取模。
int a[55];
void solve()
{
int n;
ll ans=1;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
ans*=a[i]-i+1;
ans%=1000000007;
}
cout<<ans<<endl;
}P2822 [NOIP2016 提高组] 组合数问题
P2789 直线交点数
动态规划。
f[i][j] 表示 $i$ 个直线，其中因为平行少了 $j$ 个交点，是否可能（$0$ 或 $1$）。
bitset<305>f[30];
void solve()
{
int n;
cin>>n;
f[0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i*(i-1)/2;j++)
{
if(f[i][j])
{
for(int k=1;i+k<=n;k++)
{
f[i+k][j+k*(k-1)/2]=1;
}
}
}
}
cout<<f[n].count()<<endl;
}P3913 车的攻击
没有被打到的，肯定是总数 $-$ 打到的。
所以，看有多少被打到的位置就行。
但可能会一个位置被打多次，要去重。
int x[1000005],y[1000005];
void solve()
{
ll n,k;
cin>>n>>k;
for(int i=1;i<=k;i++)
{
cin>>x[i]>>y[i];
}
sort(x+1,x+k+1);
sort(y+1,y+k+1);
int xx=unique(x+1,x+k+1)-x-1;
int yy=unique(y+1,y+k+1)-y-1;
cout<<n*n-(n-xx)*(n-yy)<<endl;
}P2638 安全系统
P1246 编码
由于这题没想到数学写法，索性暴力。
枚举所有可能，找到比输入的字符串小的，答案加上 $1$。
但是，一个迷惑的点，字符串之间比较有点怪。
下面这两行比较，就不是等价的。
cout<<((string)"z"<(string)"ab");
cout<<("z"<"ab");所以我索性自己写了个比较函数。
有个注意点，自己也算上，所以答案要加 $1$。
bool check(string st,string s)
{
if(st.size()>s.size())return 0;
if(st.size()<s.size())return 1;
return st<s;
}
void solve()
{
string s;
int ans=0;
cin>>s;
for(int i=0;i<s.size()-1;i++)
{
if(s[i]>=s[i+1])
{
puts("0");
return;
}
}
for(int i=1;i<=26;i++)
{
string st="";
st+=char(i+'a'-1);
if(check(st,s))
{
ans++;
}
}
for(int i=1;i<=26;i++)
{
for(int j=i+1;j<=26;j++)
{
string st="";
st+=char(i+'a'-1);
st+=char(j+'a'-1);
if(check(st,s))
{
ans++;
}
}
}
for(int i=1;i<=26;i++)
{
for(int j=i+1;j<=26;j++)
{
for(int k=j+1;k<=26;k++)
{
string st="";
st+=char(i+'a'-1);
st+=char(j+'a'-1);
st+=char(k+'a'-1);
if(check(st,s))
{
ans++;
}
}
}
}
for(int i=1;i<=26;i++)
{
for(int j=i+1;j<=26;j++)
{
for(int k=j+1;k<=26;k++)
{
for(int l=k+1;l<=26;l++)
{
string st="";
st+=char(i+'a'-1);
st+=char(j+'a'-1);
st+=char(k+'a'-1);
st+=char(l+'a'-1);
if(check(st,s))
{
ans++;
}
}
}
}
}
for(int i=1;i<=26;i++)
{
for(int j=i+1;j<=26;j++)
{
for(int k=j+1;k<=26;k++)
{
for(int l=k+1;l<=26;l++)
{
for(int m=l+1;m<=26;m++)
{
string st="";
st+=char(i+'a'-1);
st+=char(j+'a'-1);
st+=char(k+'a'-1);
st+=char(l+'a'-1);
st+=char(m+'a'-1);
if(check(st,s))
{
ans++;
}
}
}
}
}
}
for(int i=1;i<=26;i++)
{
for(int j=i+1;j<=26;j++)
{
for(int k=j+1;k<=26;k++)
{
for(int l=k+1;l<=26;l++)
{
for(int m=l+1;m<=26;m++)
{
for(int n=m+1;n<=26;n++)
{
string st="";
st+=char(i+'a'-1);
st+=char(j+'a'-1);
st+=char(k+'a'-1);
st+=char(l+'a'-1);
st+=char(m+'a'-1);
st+=char(n+'a'-1);
if(check(st,s))
{
ans++;
}
}
}
}
}
}
}
cout<<ans+1<<endl;
}P2926 [USACO08DEC]Patting Heads S
有点类似下一题，线性筛。
枚举每个数，那个数的倍数就答案多一。
当然，最后输出要减一，因为有自己。
int a[100005],b[1000005],ans[1000005];
void solve()
{
int n,maxx=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]++;
maxx=max(maxx,a[i]);
}
for(int i=1;i<=maxx;i++)
{
if(!b[i])
{
continue;
}
for(int j=i;j<=maxx;j+=i)
{
ans[j]+=b[i];
}
}
for(int i=1;i<=n;i++)
{
cout<<ans[a[i]]-1<<endl;
}
}P3383 【模板】线性筛素数
模板题。
线性筛，就是把一些数的倍数，打上合数的标签。
bool pri[100000005];
int a[6000000];
void init(int n)
{
pri[0]=pri[1]=1;
for(int i=2;i<=sqrt(n);i++)
{
if(!pri[i])
{
for(int cnt=2;cnt<=n/i;cnt++)
{
pri[i*cnt]=1;
}
}
}
}
void solve()
{
int n,q,sz=1;
cin>>n>>q;
init(n);
for(int i=1;i<=n;i++)
{
if(!pri[i])
{
a[sz++]=i;
}
}
while(q--)
{
int x;
cin>>x;
cout<<a[x]<<endl;
}
}P1835 素数密度
有一个做法可以直接求 $1$ 到 $n$ 个质数个数。
注意到 $R-L\leq10^6$。
注意到 $2^{31}$ 以下的合数，一定有一个 $\leq\sqrt{R}$ 的质因数。
用一个长度为 $R-L+1$ 的数组存每个数字是否是合数。
f[i] 表示 $i$ 是否是合数。
如果 f[i] == 1 表示 $L+i$ 是合数。
如果 f[i] == 0 表示 $L+i$ 是质数。
枚举所有 $\leq \sqrt{R}$ 的质数 $p$。
枚举在 $L$ 到 $R$ 之间的，所有 $p$ 的倍数（不包括 $p$ 本身）设为 $i$。
标记 $i$ 是合数.
int pri[1000005];
int v[1000005];
long long l,r,sum;
void init(long long n)
{
for(long long i=2;i<=sqrt(n);i++)
{
if(!v[i])
{
for(long long j=max((l+i-1LL)/i,2LL)*i;j<=r;j+=i)
{
pri[j-l]=1;
}
}
for(int j=i;j<=r/j;j+=i)
{
v[j] = i;
}
}
}P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
我们枚举 $P$。
判断 $P$ 是否是 $n\times m$ 的因数。
又因为 $\gcd(a,b)\times\operatorname{lcm}(a,b)=a\times b$。
所以可以算出 $Q$。
最后判断 $P$ 和 $Q$ 的最大公因数和最小公倍数即可。
当然，可以互换，答案 $\times 2$。
如果 $x=y$，答案还要 $-1$。
long long gcd(long long x,long long y)
{
return y?gcd(y,x%y):x;
}
long long lcm(long long x,long long y)
{
return x/gcd(x,y)*y;
}
void solve()
{
long long n,m,ans=0;
cin>>n>>m;
for(long long i=1;i<=sqrt(n*m);i++)
{
if(n*m%i==0&&gcd(i,n*m/i)==n&&lcm(i,n*m/i)==m)ans++;
}
cout<<(n==m?ans*2-1:ans*2)<<endl;
}P1072 [NOIP2009 提高组] Hankson 的趣味题
P1069 [NOIP2009 普及组] 细胞分裂
P1572 计算分数
P4057 [Code+#1]晨跑
三数的最小公倍数。
两两算最小公倍数，其实就是 $\operatorname{lcm}(\operatorname{lcm}(a,b),c)$。
当然，$\operatorname{lcm}(a,b)=a\div\gcd(a,b)\times b$。
所以， $\operatorname{lcm}(\operatorname{lcm}(a,b),c)=c\div\gcd(a\div\gcd(a,b)\times b,c)\times a\div\gcd(a,b)\times b$。
很简单，推一下就好。
void solve()
{
long long a,b,c;
cin>>a>>b>>c;
cout<<c/__gcd(a/__gcd(a,b)*b,c)*a/__gcd(a,b)*b<<endl;
}P1414 又是毕业季II
我们把 $n$ 个数的因数存下来，存到数组里。
就从最大的因数开始往下找，找到某个因数，出现次数正好大于等于 $k$，即为当前询问答案。
int a[1000005];
void solve()
{
int n,maxx=-1;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
maxx=max(maxx,x);
for(int j=1;j<=sqrt(x);j++)
{
if(x%j==0)
{
a[x/j]++;
a[j]++;
if(j*j==x)
{
a[j]--;
}
}
}
}
for(int i=1;i<=n;i++)
{
while(a[maxx]<i)
{
maxx--;
}
cout<<maxx<<endl;
}
}P2651 添加括号III
结论就是判断 $a_1\times a_3\times a_4 \times a_5\times...\times a_n \bmod a_2=0$ 是否成立。
因为最好的办法就是让 $a_2$ 为分母，其他为分子。
注意多组数据。
void solve()
{
int n,sum=0,a2;
cin>>n;
int x;
cin>>x>>a2;
a2/=__gcd(a2,x);
for(int i=3;i<=n;i++)
{
cin>>x;
a2/=__gcd(a2,x);
}
puts(a2==1?"Yes":"No");
}P2660 zzc 种田
每次都种若干个以宽为边长的正方形。
这样子，长变成了宽。
宽变成了原来的长种完之后剩下的长度。
过程类似于辗转相除一样。
void solve()
{
long long n,m,ans=0;
cin>>n>>m;
while(n&&m)
{
if(n>m)swap(n,m);
ans+=m/n*n*4;
m%=n;
}
cout<<ans<<endl;
}P3601 签到题
和素数密度差不多做法，不多说。
const int mod=666623333;
long long a[1000020];
long long f[1000020];
long long l,r;
int v[1000020];
void DO(long long p)
{
for(long long i=(l+p-1)/p*p;i<=r;i+=p)
{
while(a[i-l]%p==0)
{
a[i-l]/=p;
}
f[i-l]=f[i-l]/p*(p-1);
}
}
void solve()
{
scanf("%lld%lld",&l,&r);
for(int i=0;i<=r-l;i++)
{
a[i]=l+i;
f[i]=l+i;
}
for(int i=2;i<=r/i;i++)
{
if(!v[i])
{
DO(i);
}
for(int j=i;j<=r/j;j+=i)
{
v[j]=i;
}
}
long long z=(l+r)%mod*(r-l+1)%mod*333311667%mod;
for(int i=0;i<=r-l;i++)
{
if(a[i]>1)
{
f[i]=f[i]/a[i]*(a[i]-1);
}
z=(z-f[i])%mod;
}
printf("%lld\n",(z+mod)%mod);
}P1403 [AHOI2005]约数研究
每 $x$ 个数中，就有 $1$ 个 $x$ 的倍数。
枚举约数，用 $n$ 去除一下，就知道有多少个倍数。
void solve()
{
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
ans+=n/i;
}
cout<<ans<<endl;
}