牛客多校第三场
1.
思想: 指数循环节-欧拉函数的性质-数论
题目:Graph Games
链接:https://ac.nowcoder.com/acm/contest/883/D
大意:求有多少个(i,j)满足i∈[1,n],j∈[1,m](n∈[1,1e9],m∈[1,1e9]),A(i^j)=0modp(p是质数,p∈[1,1e9]),其中A(x)表示
一个十进制数字，由x个'1'组成
分析:A(i^j)=0(mod p) 
因为p是质数,
所以若p==2||p==5,10^(i^j)对mod 9*p没有逆元
除此之外,我们要求要求得ans,要求得最小的s使10^s=1 mod(9*p)，即求指数循环节
在求指数循环节之前，要求得9*p得欧拉函数，因为10^
再加上欧拉函数是积性函数,
所以,若p=3,则
若p!=3,则
求得
求得指数循环节,接下来就是求有多少(i,j)满足 i^j = 0 mod sma
这个时候，又要将sma因数分解,得到sma的分解式
对于特定的j,可以算出 i中包含的pi的次数至少
我写的比较繁琐,不建议大家看(除非你只看得懂我的代码):
/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define F0(i, a, n) for (ll i = (a); i < (n); i++)
#define F(i,a,b) for(ll i=(a);i<=ll(b);++i)
#define FN(i,a,b) for(ll i=(a);i>=ll(b);--i)
//简化敲击
#define PII pair<int,int>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<iostream>
#include<iomanip>
#include<string>
#include<stdio.h>
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
template<typename INint> inline void OUT(INint x)
{
if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(20);
ll n, m, p;
ll qpow(ll a, ll b, ll p) //求a^bMODp
{
ll ret = 1; a %= p;
while (b)
{
if (b & 1)ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
return ret;
}
void getfac(ll val, vector<ll>&vec, vector<ll>¶)
{
vec.clear(); para.clear();
for (ll i = 2; i*i <= val;)
{
if (val%i == 0)
{
ll cnt(0);
while (val%i == 0)
{
++cnt;
val /= i;
}
vec.push_back(cnt); para.push_back(i);
}
else ++i;
}
if (val != 1)
{
vec.push_back(1);
para.push_back(val);
}
}
ll calEura(ll n)
{
if (n == 1)return 1;
ll ret(n);
for (ll i = 2; i*i <= n;)
{
if (n%i == 0)
{
ret = ret - ret / i;
while (n%i == 0)
{
n /= i;
}
}
else ++i;
}
if (n != 1)
{
ret = ret - ret / n;
}
return ret;
}
ll askP2(ll p)
{
ll E = 6*(p - 1);
ll xun=E;
vector<ll>in;
for (ll i = 2; i*i <= E; ++i)
{
if (E%i == 0) {
in.push_back(i);
if (qpow(10, i, p) == 1)
{
xun = i;
break;
}
}
}
if (xun == E)
{
reverse(in.begin(), in.end());
for (auto x : in)
{
x = E / x;
if (qpow(10, x, p) == 1)
{
xun = x;
break;
}
}
}
return xun;
}
void solve()
{
ll xun;
if (p % 2 == 0 || p % 5 == 0)
{
cout << 0 << '\n';
return;
}
else if (p == 3)xun = 3;
else
{
xun = askP2(p);
}
vector<ll>vec, para;
getfac(xun, vec, para);
ll ans(0);
if (m < 32)
{
F(j, 1, m)
{
ll pro(1);
F(i, 0, vec.size() - 1)
{
ll mi = 0;
while (mi*j < vec[i])++mi;
while (mi--)pro *= para[i];
}
ll cnt = n / pro;
ans += 1ll * cnt;
}
}
else
{
F(j, 1, 32)
{
ll pro(1);
F(i, 0, vec.size() - 1)
{
ll mi = 0;
while (mi*j < vec[i])++mi;
while (mi--)pro *= para[i];
}
ll cnt = n / pro;
ans += 1ll * cnt;
}
{
ll pro(1);
F(i, 0, vec.size() - 1)pro *= para[i];
if (pro <= n)
{
ll cnt = n / pro;
ans += 1ll * (m - 32)*cnt;
}
}
}
//int ans2(0);
//F(i, 1, n)
// F(j, 1, m)
// if (qpow(i, j, p2) == 0)
// {
// ++ans2;
// //cout << i << ' ' << j << endl;
// }
//cout << endl;
////assert(ans == ans2);
//cout << ans2 << ' ';
cout << ans << '\n';
}
#define endl '\n'
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
#ifndef endl
freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
cout << "************************************Local Test*********************************" << endl;
#endif // !endl
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T(1), cas(0);
cin >> T;
/////////////////////////////////////////////////////////////////////////////////////////////////
while (cas, T--)
{
cin >> p >> n >> m;
solve();
}
///////////////////////////////////////////////////////////////////////////////////////////////////
return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/
2.
思想:单调队列-矩阵最值-统计
题目:F.Planting Trees
链接:https://ac.nowcoder.com/acm/contest/883/F
大意:给一个矩阵(n<=500),矩阵中的值∈[1,1e5],给定M∈[1,1e5],求最大(连续)子矩阵面积使(连续)子
矩阵中元素最大值最小值之差不超过M,题目明显暗示复杂度限制在N^3
分析:看的第一眼,我就知道:我只会N^4的做法,n^3我不会，弃了
假的，后来看了题解，题解做法是维护两个单调队列(我比赛的时候只想到了用一个单调队列，但是一个单调队列怎么维护两个属性?用结构体?,总之就是很迷)。
题解的做法是先抛出每一个第i行的所有[le,ri]区间的Min和Max值，也就是对于每一个(i,le,ri)三元组记录一个min和max值,然后对于每一个le,ri，按序遍历每一行，维护min值上升,max下降的2个单调队列，然后计算当前的i的矩阵向上最大能延伸到多小的i。队首维护单调队列的单调性，队尾维护从当前行能向上延伸的最小行(我是从队首推入的)(根据当前行的min和max值)
TQL(对了这题还卡常，要滚动数组，还要手工队列，还要cache友好)
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=ll(b);++i)
#define MODY(n) (n%=mod)<0?n+=mod:n
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = int(550);
int val[maxn][maxn];
int Mi[maxn][maxn], Ma[maxn][maxn];
int N, M;
int ma[maxn], mi[maxn];
template<typename INint> inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
int main()
{
//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T(1), cas(0);
cin >> T;
while (cas, T--,cin>>N>>M)
{
F(i, 1, N)F(j, 1, N)
IN(val[i][j]);
int ans(0);
F(le, 1, N)
{
F(j, 1, N)Ma[le][j] = Mi[le][j] = val[le][j];
F(ri, le + 1, N)
F(j, 1, N)
{
Ma[ri][j] = max(Ma[ri - 1][j], val[ri][j]), Mi[ri][j] = min(Mi[ri - 1][j], val[ri][j]);
}
F(ri, le, N)
{
int Rma(0), Lma(1), Rmi(0), Lmi(1);
int to(0);
F(i, 1, N)
{
while (Rma >= Lma && Ma[ri][i] > Ma[ri][ma[Rma]])--Rma;
ma[++Rma] = i;
while (Rmi >= Lmi && Mi[ri][i] < Mi[ri][mi[Rmi]])--Rmi;
mi[++Rmi] = i;
while (Rma >= Lma && Rmi >= Lmi && Ma[ri][ma[Lma]] - Mi[ri][mi[Lmi]] > M)
{
++to;
if (ma[Lma] <= to)++Lma;
if (mi[Lmi] <= to)++Lmi;
}
ans = max(ans, (ri - le + 1)*(i - to));
}
}
}
cout << ans << '\n';
}
return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/ 其他的懒得写题解了(大部分是不会)
