---恢复内容开始---
话说要学反演了，contest一题都搞不定，整理题目暂且搁置，数学笨蛋来学一下数学_(:з」∠)_
---恢复内容结束---
是的，预习看了半天教学，没有整理，做题又都不会，我能怎么办呢_(:з」∠)_我只能补题了呀
HDU-3903 结论题，易证
首先由余弦定理，abc都是有理数所以cosA是有理数；然后由数学归纳法知cos nA也是有理数。cos（+）也可以化成一堆cos，所以分子是有理数。
对于分母，我们可以由sin2+cos2=1直接得到sin2=4a2b2-（a2+b2-c2）2，因为显然原本的分母4a2b2为有理数，就减少运算吧。
常用的判断无理数的方法：非完全平方数被开方，利用精度，通过sqrt后再平方判断是否在一定精度内相等来判断是否是完全平方数的开方，即是否为有理数。
拍下乱码，为了精度全部开成了long long(๑•̀ㅂ•́)و✧
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long long a, b, c, m, n, k; int main() { int t; cin >> t; while (t--) { cin >> a >> b >> c >> m >> n >> k; long long p,q; p = 4 * a*a*b*b - (a*a + b * b - c * c)*(a*a + b * b - c * c); q = sqrt(1.00*p); if (q*q == p)cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
HDU-6069 一个数可以拆分为一些素数的次方的乘积，并且这个数的不同因子的个数为各个次方加一的乘积
意思是：n=p1a1p2a2……的不同因子个数为（a1+1）*（a2+1）……显然n的k次方会使（a*k+1）
数据略大，同时给了提示即R与L的差值，发现差值可以编号。
但是如果对每个i都查一遍表的话仍然会亡，“跳“”着来，即查一遍表，把符合条件的i都维护一遍，最后大家都获得了自己的因数_(:з」∠)_
感谢https://www.cnblogs.com/stepping/p/7357193.html题解，让我明白了上面一点。
//两三天后红小豆终于做出来这题，我不会告诉你t了多少次才找到那个假装自己是l的1，一度怀疑自己背的素数板子的速度（dying
#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; const ll mod = 998244353; ll l, r, k; ll p[100005]; bool isp[1000005]; ll ans[1000005], n[1000005]; int co; void pri() { for (int i = 2; i < 1000000; i++) isp[i] = 1; co = 0; for (int i = 2; i < 1000000; i++) { if (isp[i])p[co++] = i; for (int j = 0; j < co&&i*p[j] < 1000000; j++) { isp[i*p[j]] = 0; if (i%p[j] == 0)break; } } return; } int main() { pri(); int t; cin>>t; while (t--) { cin>>l>>r>>k; for (int i = 0; i <= r - l; i++) { ans[i] = 1; n[i] = l + i; } for (int i = 0; i < co; i++) { ll h = (l / p[i])*p[i]; if (h < l)h += p[i]; for (ll j = h; j <= r; j += p[i]) { ll q = 0; while (n[j - l] % p[i] == 0) { n[j - l] /= p[i]; q++; } ans[j - l] = ans[j - l] * (q*k + 1) % mod; } } ll a = 0; for (int i = 0; i <= r - l; i++) { if (n[i] > 1)ans[i] = ans[i] * (k + 1) % mod; a = (a + ans[i]) % mod; } cout<<a<<endl; } return 0; }
因为是自己又写了一遍，注意到了一些细节，比如作为起始点的h在循环j的时候也会用到，所以j要开longlong不然会re，最后那个循环放在一起纯属本人的连连看属性（没看上述题解的无视这条）owo。还有mod的时候*=和+最好不要用呢，会少mod的。最重要的一点是，有1无l，有l无1，切记切记_(:з」∠)_
HDU-5187 组合数 快速乘 快速幂
搜题解的时候看到状压dp是非常懵的，然后发现那是兄弟题。。。
快速乘快速幂我都懂，但是看不懂怎么就开始组合数求和了。。。总之manage to 理解了。
首先要知道（0，n）+（1，n）+...+（n，n）=2^n。小括号是组合数的一种表达方式嗯。
其次，这个东西可以这么理解：从n个数中选出0个数作为增序列（or减），剩下n个为减（or增）
从n个数中选出1个数作为增，剩下n-1个为减……以此类推
可以发现从0到n把全体序列单调增/减算了两次，所以最后再减2.（就是（1，n）和（n-1，n）的时候啦）(๑•̀ㅂ•́)و✧
#include<iostream> #include<cstdio> #include<cmath> using namespace std; typedef unsigned long long ull; ull mul(ull a, ull b,ull p) { ull ans = 0; while (b) { if (b & 1) { ans = (ans + a) % p; b--; } a = (a + a) % p; b >>= 1; } return ans; } ull pw(ull a, ull b,ull p) { ull ans = 1; while (b) { if (b & 1) { ans = mul(ans, a, p); b--; } a = mul(a, a, p) ; b >>= 1; } return ans; } int main() { ull n, p; while (cin >> n >> p) { if (n == 1) { if (p == 1)cout << 0 << endl; else cout << 1 << endl; continue; } cout << (pw(2, n, p) - 2+p)%p << endl; } return 0; }
看到1e18就是想开ull。快乘快幂里面的b--其实不是必须的，在最后移位（除以2）的时候自然会被弄掉。还有特判情况结束记得return或者continue。
重点是，有mod有减的时候，千万要，+mod再mod一次！！！
HDU-5019 gcd 分解因数
有个循环的i要开ll，别的没什么。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll f[100005]; int co; ll g(ll a, ll b) { return b == 0 ? a : g(b, a%b); } void de(ll n) { co = 0; for (ll i = 1; i*i <= n; i++) if (n%i == 0) { f[co++] = i; if (i*i != n)f[co++] = n / i; } return; } int main() { int t; ll x, y, k; cin >> t; while (t--) { for (int i = 0; i <= 100005; i++)f[i] = 0; cin >> x >> y >> k; ll n; n = g(x, y); de(n); if (k > co) { cout << -1 << endl; continue; } sort(f, f + co); cout << f[co - k] << endl; } return 0; }