Posts match “ 数论 ” tag:

http://poj.org/problem?id=1845

主要是利用因子和公式。

这里给出三种方法,三份代码。

首先特判a%mod==1的情况,详见代码;注意到mod=9901是个质数,刚好前面的特判可以保证gcd(指数-1,9901)==1,所以可以直接求逆元。(用扩展欧几里得或者费马小定理均可)

如若题目所给的mod不是质数,该怎么做?更通用的解法是?
这时我们可以套用级数求和公式。

继续阅读

http://codeforces.com/problemset/problem/338/D

由于gcd(i,j)为i的因子,所以拿样例1来说,5,2,1均为行号的因子,所以行号至少是lcm(5,2)=10的倍数。
推而广之,行号至少是的倍数。

再看列号。
由于gcd(i,j)同时又为j的因子,设序列最左边的数的列号为j,则有

所以有

解此同余方程组即得j

最后判断下j+k-1是否<=m

陷阱:

  1. 求lcm需中途判断是否会超long long;
  2. 求出j后还要验证下能否还原出a数组,如果还原不了,由于这一行的数是周期性的,所以后面的j也不能满足,故输出NO
继续阅读

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1632

我们发现n*(n-1)*(n-2)的乘积最大,如果这三个数还两两互质的话那就最棒了。

  1. 如果n是奇数,那么n,n-1,n-2必定两两互质,ans=n*(n-1)*(n-2) 证明:n是奇数,那么n,n-1,n-2一定是两奇加一偶的情况,所以2不可能是公因子。假设p(p>2)是公因子,a,b是n,n-1,n-2中两个不同的数,那么a-b≡0(mod p),这不可能。
  2. 如果n是偶数,这样的话n和n-2必定有公因子2,那么就换成式子n*(n-1)*(n-3)。
  3. 然后仔细思考一下,不行啊,若n本身就能被3整除的话,那么n和n-3就有公因子3。再仔细思考一下,可以得出ans=(n-1)*(n-2)*(n-3),两奇夹一偶的情况。
继续阅读

http://codeforces.com/gym/100463

切了场GYM。

A题
简单树状数组。

C题
首先对每个点连出的边进行极角排序(范围内),由于题意是逆时针旋转,我们可以G[i][angle[j].y] = angle[j + 1].y;这样用邻接矩阵建图。
建好图后 DFS 下就可以求出所有圈的长度了。

(顺便吐槽下此题时限为 40 s)

D题
直接枚举红点一半的组合就行,不需要判断是否有其他红点在所选的红点围成的矩形内,因为在这种情况下,一定有比该矩形更小的矩形。

E题
并查集。合并的时候要讨论清楚:

  1. 当 x==y 时集合唯一确定,用一个布尔数组 uni 表示(uni 表示 unique);
  2. merge 时要合并人数,集合大小,uni 这三个。

I题
这题需要有特殊的 YY 技巧。
由于要使A集合与B集合扩张成一个对减法封闭的,所以必须要有单位元 1 和 -1,进一步分析发现我们要判断出是否可以从A集合中可重复地取出 x 个数,从B集合中可重复地取出 x-1 或 x 个数,使得对于某些取法 sumA-sumB=1,某些取法 sumA-sumB=-1。

显然答案与有关,设其值为g,则 g=1 时可以扩张成;由于还可以先往右边多走一步,则 g=2 且集合A中存在奇数时也可以扩张成(g=2 说明可以扩展成偶整数集合,此时只要集合A中有个奇数就可以扩张成);但是对于 g>2 的情况却不行,这是因为此时扩张成 {...,-2g,-g,0,g,2g,...} 的集合,但又由于,所以,令,则只能扩张成形如 mg+k 的集合。
优化:

  1. 可以简化为
  2. 根据此简化式,判断集合A中是否有奇数可以简化为判断是否为奇数;
  3. 判断

附代码:

继续阅读

int solve(int n)
{
    int sqrtn = sqrt(n + 0.5), cnt, ans = 1;
    for (int i = 2; i <= sqrtn; ++i) if (n % i == 0)
        {
            for (n /= i, cnt = 1; n % i == 0; n /= i) ++cnt;
            if ((i & 3) == 1) ans *= cnt << 1 | 1;
        }
    if (n > 1 && (n & 3) == 1) ans += ans << 1;
    return (ans - 1) >> 1;
}

使用 Pollard's rho 算法可以加速到,代码就不贴了。。

参考 A046080 中的 Mathematica 代码:

cnt[n_] := If[n == 1, 0, With[{expList = Select[FactorInteger[n], Mod[#[[1]], 4] == 1 &][[All, 2]]}, ((Times @@ (2 * expList + 1)) - 1) / 2]];

证明待填。。

原根:定义见 wiki,这里只补充讲解数 的原根的求法.

首先我们肯定要从 开始枚举 的原根 (或者rand()),关键在于怎么验证某一个数是不是一个原根:

  1. 最暴力的方法就是暴力枚举 范围内的指数,看有是不是所有结果都不模 .
  2. 优化:我们可以只枚举 的因子,因为 的阶 满足 .
    反证:若 ,则设 ,这里 .
    那么 ,这与 矛盾.
  3. 继续优化:我们可以只枚举 的质因子 ,如果 ,那么 是模 的原根.
    还是反证:在 的情况下,若 不是模 的原根,那必然有 .
    由 2 知 ,故设 ,再设 的一个因子,那同时 也是 的一个因子,所以 ,矛盾.

这样求原根就会非常之快了.

未完待续。。。