完成题目：洛谷×7

欧拉筛

for(int i=2;i<=M;i++){//M为上限
    if(!vis[i])P[++tot]=i;
    for(int j=1;j<=tot;j++){
        if(P[j]*i>M)break;
        vis[P[j]*i]=true;
        if(i%P[j]==0)break;
    }
}

以上为主要代码
某一个合数被筛掉时P[j] *i 中P[j] 一定为它的最小的质因数
假设有一个合数 F=(a^x1)(b^x2)(c^x3)
a b c都是质数且a<b<c
假设i=(a^x1)(c^x3)
当质数判断到P[j]=a的时候就会因为i%P[j]=0而退出，所以P[j]不会判断到P[j]=b，从而使F多判断一次
当i=(a^(x1-1))(b^x2)(c^x3)时，i的最小质因数为a或者b，所以一定会把a*i 判断为合数，然后在P[j]=a或者b的时候退出
综上，F只会被判断一次，且必定会被判断到

__int128

__int128 数据的范围是 $[(-2)^{127} ,2^{127}-1]$
输入就用快读
输出代码：

void Print(__int128 x)
{
    if (x<0) {putchar('-');x=-x;}
    if (x>9)Print(x/10);
    putchar(x%10+'0');
}

注意！！！第二行是 x>9 而不是 x>0
当 0<=x<=9的时候就不用继续往下调用函数了，可以直接输出了

P2789 直线交点数

题目描述

假设平面上有 $N$ 条直线，且无三线共点，那么这些直线有多少种可能的交点数？

输入格式

一行，一个整数 $N$，代表有 $N$ 条直线。

输出格式

一行，一个整数，表示方案总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

对于所有数据，满足 $1 \le N \le 25$。

题解

假设n条线共有x种状态（同种状态意味着平行）
那么假设每种状态有$a1,a2,a3,……,ax$条线（$\sum{a_i}=n$）
那么这种情况总相交点数为$\sum_{i=1}^{x}{(a_i*\sum_{j=1}^{i-1}{a_j})}$（可以自己推一下）

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const int N=1e6+10;
int n,vis[N],ans;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void dfs(int x,int t)
{
	if(x==n){
		if(!vis[t])vis[t]=true,ans++;
		return;
	}
	for(int i=1;i<=x;i++){
		if(x+i>n)break;
		dfs(x+i,t+i*x);
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)dfs(i,0);
	cout<<ans;
	return 0;
	
}

P2638 安全系统

题目描述

特斯拉公司的六位密码被轻松破解后，引发了人们对电动车的安全性能的怀疑。李华听闻后，自己设计了一套密码：

• 假设安全系统中有 $n$ 个储存区，每个储存区最多能存储存 $2$ 个种类不同的信号（可以不储存任何信号）。有 $0$ 和 $1$ 这两种信号，其中 $0$ 有 $a$ 个，$1$ 有 $b$ 个，单独一个 $0$ 或 $1$ 算一个信号。现要将这些信号储存在储存区中，$0$ 和 $1$ 可以不用全部储存，一个存储区可以存放任意多个 $0$ 和任意多个 $1$。一种不同的储存方案经过李华处理后就将是一串不同的密码。
  现在给出 $n,a,b$，求可能的不同储存方案的个数。

输入格式

第一行：共 $3$ 个整数，$n,a,b$。

输出格式

第一行：一个整数，表示方案个数。

样例 #1

样例输入 #1

2 1 1

样例输出 #1

9

提示

所有 $9$ 种方案如下：

对于全部数据，$a,b\le 50$，$n+a\le 50$，$n+b\le 50$。

题解

$0$和$1$可以分开来看
分别求$0$和$1$在各个储存区的情况数，最后相乘即为答案
假设这里有$x$个$1$需要分配到$n$个储存区（$x$个$1$不用全部分配，也可不分配）

隔板法：

假设有$m$个球要放进$n$个篮子里，第$n_i$个篮子至少要$p_i$个球
那么情况数为：$C_{m-\sum_{i=1}^{n}{(p_i-1)}-1}^{n-1}$
意思是每个篮子先放入$p_i-1$个球，然后用$n-1$个隔板把剩下的球隔开，这样一定符合条件（注意若剩下$c$个球那么它们中间只有$c-1$个空格，所以答案是$C_{c-1}^{n-1}$而不是$C_{c}^{n-1}$）

用隔板法应用到此题，首先$p_i$都为零
假设有恰好$c(c<x)$个$1$需要被分配到$n$个储存区，那么可以用隔板法算出答案
这种情况下方案数为：
$C_{c-n*(p_i-1)-1}^{n-1}=C_{c+n-1}^{n-1}$

那么从$1$开始枚举$c$到$x$，求和即是答案
所以对于分配$1$的方案数为（$1$一共有$x$个）：$\sum_{i=1}^{x}{(C_{i+n-1}^{n-1})}$

因为题中所给$0$有$a$个，$1$有$b$个，所以总方案数为：
$\sum_{i=1}^{a}{(C_{i+n-1}^{n-1})*\sum_{i=1}^{b}{(C_{i+n-1}^{n-1})}}$

注意本题数据太大，需要用到__int128

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const int N=1e6+10;
__int128 num1,num2,c[70][70],n,a,b;
inline __int128 read()
{
    __int128 f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void Pre()
{
	for(int i=1;i<=50;i++){
		c[i][0]=1,c[i][1]=i;
		for(int j=2;j<=i;j++)
			c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
}
void Print(__int128 x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)Print(x/10);
	putchar(x%10+'0');
}
int main()
{
	n=read(),a=read(),b=read();
	Pre();
	for(int i=0;i<=a;i++)num1+=c[i+n-1][n-1];
	for(int i=0;i<=b;i++)num2+=c[i+n-1][n-1];
	__int128 x=num1*num2;Print(x);
	return 0;
}