什么是逆元？

乘法逆元：

• 模p意义下，一个数a如果有逆元x，那么除以a相当于乘以x。
• 在模n的意义下，a存在逆元的充要条件是**n不等于1，且（a，n）互质。怎样求逆元？

1. 费马小定理（有限制）
   =》p为素数时，a关于mod p的逆元为a^(p-2)mod p。用快速幂模。
2. 扩展欧几里得算法（普遍适用）

• 给定模数n，求a的逆元
• 即ax=1(mod n)
• =》ax-ny=1
• 所以可用扩展欧几里得， ax+by=gcd（a，b）求逆元，即求x的值。注意：存在逆元的判断条件是 a，m互质。

if(gcd(a,m) != 1)       //a，m不互质，则不存在逆元
 cout << "Not Exist" << endl;
 else
 {
      ext_gcd(a, m, x, y);
      LL ans = (x<=0) ? (x%m+m) : x;  //有可能x是负数，x要先取模再加
      cout << ans << endl;

终于结果出来了，看看今年的评分规则和奖项分布。

CCF NOI科学委员会、竞赛委员会召开会议，确定了CCF CSP-J/S2019第二轮评级规则及评级名额方案。

提高级一等名额分配方案

提高级一等全国认证基准线:165分

CCF CSP-J/S第二轮（提高级）省一等名额由三部分组成：

A：第二轮人数和省平均分；

B：第一轮人数；

C：第一轮晋级第二轮比例。

计算规则如下：

1.确定全国认证基准分数线、拟评级比例为20%，根据各省第二轮提高级人数Q、平均分R，一个省可获名额A的计算公式如下：

A=((省第二轮平均分R－全国一等认证基准线)×0.1%+20%)×省第二轮提高级人数Q

注：0.1%为比例因子（省平均分与全国一等认证基准线之差，每增加10分，评级比例增加1%）；

2.根据省第一轮人数（P），可计算一个省获得的相应名额B：

（1）.0＜P＜5000，B=(S－全国A名额总和)×第一轮人数P/全国第一轮总人数

（2）.P≥5000时，每增加2700人，增加1个名额；

注：S为拟评级人数，定义为2700；

3.根据省第一轮晋级第二轮比例（M），全国第一轮晋级第二轮最低比例20%，可计算一个省获得的相应名额C。即，除各省第一轮晋级第二轮比例M低于全国最低比例20%以下的（不含）省份外，其他省分别获得1个C名额。在此基础上，省晋级比例M比全国最低比例20%每高5%再奖励1个C名额，M上限80%。名额C不超过各省（市）计算名额AB之和的40%。

（1）.0＜M＜20%，C=0

（2）20%≤M≤80%时，C=((M-20%)/5%)+1

以上A、B、C之和为各省第二轮提高级一等参考名额，科学委员会、竞赛委员会根据各省认证成绩、评级人数及比例适当调整。

说明：

1.第一轮人数、第二轮人数按实际参加者（零分者包括在内）计算；

提高级二等名额分配方案

提高级二等全国认证基准分数线: 110分

1.提高级一等认证分数线位于基准分数线165分（含）以上的省份，110分（含）以上未获一等者均可评二等；

2.对于提高级一等认证分数线低于基准分数线的省，80分（含）以上的认证者未获一等者均可评二等；

提高级三等名额分配方案

1.提高级一等认证分数线在基准分数线165分（含）以上的省份，80分（含）以上未获一二等的认证者，均可评三等。

2.一等认证分数线低于全国基准分数线的省份，不设三等。

入门级一等名额分配方案

入门级一等全国基准分数线：150分

CSP-J/S2019第二轮入门级一等名额分配方案同提高级一等计算方式。

入门级二等名额分配方案

入门级二等全国基准分数线：100分

1.入门级一等评级分数线位于基准分数线150分（含）以上的省份，100分（含）以上未获一等者均评获二等。

2.对于入门级一等评级分数线低于基准分数线的省，70分（含）以上未获一等者均可评二等；

入门级三等名额分配方案

1.入门级一等评级分数线位于全国基准分数线150分（含）以上的省份，70分（含）以上未获一二等的认证者，均可评三等。

2.入门级一等评级分数线低于全国基准分数线的省份，不设三等；

NOI各省组织单位根据上述提高级二三等、入门级二三等评级办法，可结合本省（市）实际情况上调评级分数线，确定本省分数线及认证名单，于12月10日12:00前上报CCF 。

中国计算机学会

2019年12月9日

附：CSP-J/S2019第二轮提高级一等各省评级分数线

（按分数线由高到低降序排列）

 一等评级总人数为2859人，总比例为20.56%

CSP-J/S2019第二轮入门级一等各省评级分数线

（按分数线由高到低降序排列）

 一等评级总人数为3215人，总比例为20.98%