2019牛客暑期多校训练营（第三场） - D - Big Integer - 数论
https://ac.nowcoder.com/acm/contest/883/D
\(A(n)\) 是由n个1组成的一个整数。
第一步：把 \(A(n)\) 表示为 \(\frac{10^n-1}{9}\) （第一步都想不出来）
那么 \(A(n)=0\;mod\;p\) ，当9和p互质的时候，存在一个 \(inv9\) ，那么原式即 \((10^n-1)*inv9=0\;mod\;p\)
两边乘9，移项得 \(10^n=1\;mod\;p\)
由欧拉定理，得 \(10^n=10^{n\;mod\;p-1}\;mod\;p\)
即这样的n必定是循环的，取 \(p-1\) 以内的一个研究
由费马小定理 \(a^{p-1} = 1\;mod\;p\) ，这样的n存在，且 \(n=p-1\)
这样，随着n增加，模p的余数必定是循环的，循环节的长度至多为 \(p-1\) ，那会不会有更短的呢？
考虑 \(d|p-1\) ，那么可以变形为 \(10^{p-1}=10^{d\frac{p-1}{d}}\;mod\;p\) 即 \((10^\frac{p-1}{d})^{d}=1\;mod\;p\)
这样最小的循环节必定是 \(p-1\) 的因数（赛中有发现），\(O(\sqrt {p})\) 枚举d，\(O(logd)\) 验证其是否是循环节（直接快速幂看看是不是和 \(10^0=1\;mod\;p\)一样就可以了）
目前复杂度\(O(\sqrt {p} logp)\)
找到最小的循环节之后，考虑怎么计数。那当然是要求 \(d|n\) 的个数，这样的（正整数）n明显在m以内有 \(\lfloor\frac{m}{d}\rfloor\)个。
但是套上 \(n=i^j\) 之后呢？猜测和d的质因数分解有关（赛中有发现）。
考虑i的质因数分解 \(i=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}\)
则 \(i^j=p_1^{ja_1}p_2^{ja_2}p_3^{ja_3}...p_k^{ja_k}\)
分解d \(d=p_1^{b_1}p_2^{b_2}p_3^{b_3}...p_k^{b_k}\)
整除的条件，d是n的因子，则n的各个质因子覆盖d，即 \(ja_x>=b_x\) 对所有的 \(1<=x<=k\) 成立。
最值得学习的技巧来啦：考虑固定住j，那么合法的i满足什么条件才能满足上式呢？是d的每种质因子\(p_x\)，i都至少要有\(\lceil\frac{b_x}{j}\rceil\)个
把这个值单独抽出来记为g \(g=p_x^{\lceil\frac{b_x}{j}\rceil}\)，i要覆盖g，则\(g|i\)，这样的i在n范围内有\(\lfloor\frac{n}{g}\rfloor\)个。
那么单个j的情况可以遍历d的质因子（分解的复杂度被上面对p的分解吸收，而分解后至多十几种质因子）求出。
当j变化时也会引起g的变化，具体来说每次j的变化可能会导致一些指数变小，但其实指数的总和至多就30多，也就是可以暴力对j进行统计。
在j超过最大的\(b_x\)之后，这样g变成1然后不再改变，以后的i都有n个。
那么特例为什么有2,3,5呢？首先3和9不互质，不存在这样的inv9，所幸3的倍数的各位数字之和都是3的倍数，考虑固定j=1,那么ans+=n/3，当j=2的时候，分别有1，4，9，16，25，36，一个不严谨的办法是继续ans+=n/3，而j=3的时候，分别是1，8，27，64，125，216，也是ans+=n/3。所以干脆就ans=(n*m)/3。
当2和5的时候， \(10^n = 1\;mod\;p\) 显然不可能成立，因为 \(10^n = 0\;mod\;p\) 显然成立。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int x = 0;
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}
int qpow(ll x, int n, int p) {
ll res = 1;
while(n) {
if(n & 1)
res = res * x % p;
x = x * x % p;
n >>= 1;
}
return res;
}
const int INF = 1e9 + 1;
int find_d(int p) {
int n = p - 1, d = INF;
for(int i = 1; i * i <= n; ++i) {
if(n % i == 0) {
if(qpow(10, i, p) == 1)
return i;
if(i * i != n) {
if(qpow(10, n / i, p) == 1) {
d = min(d, n / i);
}
}
}
}
return d;
}
int pk[50], bk[50], k;
int factor(int n) {
int maxbk = 0;
k = 0;
for(int i = 2; i * i <= n; ++i) {
if(n % i == 0) {
++k;
pk[k] = i;
bk[k] = 0;
while(n % i == 0) {
++bk[k];
n /= i;
}
maxbk = max(maxbk, bk[k]);
}
}
if(n != 1) {
++k;
pk[k] = n;
bk[k] = 1;
maxbk = max(maxbk, bk[k]);
}
return maxbk;
}
ll solve(int p, int n, int m) {
int d = find_d(p);
if(d == INF)
return 0;
int maxbk = factor(d);
ll ans = 0;
for(int j = 1; j <= m; ++j) {
int g = 1;
for(int i = 1; i <= k; ++i) {
g = g * qpow(pk[i], (bk[i] + j - 1) / j, p);
}
ans += n / g;
if(j >= maxbk) {
ans += 1ll * (m - j) * (n / g);
return ans;
}
}
return ans;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int T = read();
while(T--) {
int p = read(), n = read(), m = read();
ll ans = 0;
switch(p) {
case 3:
ans = 1ll * (n / 3) * m;
break;
case 2:
break;
case 5:
break;
default:
ans = solve(p, n, m);
}
printf("%lld\n", ans);
}
}
既然有dalao喜欢开源模板……
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40924149
include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
typedef pair<ll,ll> PLL;
namespace Factor {
const int N=1010000;
ll C,fac[10010],n,mut,a[1001000];
int T,cnt,i,l,prime[N],p[N],psize,_cnt;
ll _e[100],_pr[100];
vector<ll> d;
inline ll mul(ll a,ll b,ll p) {
if (p<=1000000000) return a*b%p;
else if (p<=1000000000000ll) return (((a*(b>>20)%p)<<20)+(a*(b&((1<<20)-1))))%p;
else {
ll d=(ll)floor(a*(long double)b/p+0.5);
ll ret=(a*b-d*p)%p;
if (ret<0) ret+=p;
return ret;
}
}
void prime_table(){
int i,j,tot,t1;
for (i=1;i<=psize;i++) p[i]=i;
for (i=2,tot=0;i<=psize;i++){
if (p[i]==i) prime[++tot]=i;
for (j=1;j<=tot && (t1=prime[j]*i)<=psize;j++){
p[t1]=prime[j];
if (i%prime[j]==0) break;
}
}
}
void init(int ps) {
psize=ps;
prime_table();
}
ll powl(ll a,ll n,ll p) {
ll ans=1;
for (;n;n>>=1) {
if (n&1) ans=mul(ans,a,p);
a=mul(a,a,p);
}
return ans;
}
bool witness(ll a,ll n) {
int t=0;
ll u=n-1;
for (;~u&1;u>>=1) t++;
ll x=powl(a,u,n),_x=0;
for (;t;t--) {
_x=mul(x,x,n);
if (_x==1 && x!=1 && x!=n-1) return 1;
x=_x;
}
return _x!=1;
}
bool miller(ll n) {
if (n<2) return 0;
if (n<=psize) return p[n]==n;
if (~n&1) return 0;
for (int j=0;j<=7;j++) if (witness(rand()%(n-1)+1,n)) return 0;
return 1;
}
ll gcd(ll a,ll b) {
ll ret=1;
while (a!=0) {
if ((~a&1) && (~b&1)) ret<<=1,a>>=1,b>>=1;
else if (~a&1) a>>=1; else if (~b&1) b>>=1;
else {
if (a<b) swap(a,b);
a-=b;
}
}
return ret*b;
}
ll rho(ll n) {
for (;;) {
ll X=rand()%n,Y,Z,T=1,*lY=a,*lX=lY;
int tmp=20;
C=rand()%10+3;
X=mul(X,X,n)+C;*(lY++)=X;lX++;
Y=mul(X,X,n)+C;*(lY++)=Y;
for(;X!=Y;) {
ll t=X-Y+n;
Z=mul(T,t,n);
if(Z==0) return gcd(T,n);
tmp--;
if (tmp==0) {
tmp=20;
Z=gcd(Z,n);
if (Z!=1 && Z!=n) return Z;
}
T=Z;
Y=*(lY++)=mul(Y,Y,n)+C;
Y=*(lY++)=mul(Y,Y,n)+C;
X=*(lX++);
}
}
}
void _factor(ll n) {
for (int i=0;i<cnt;i++) {
if (n%fac[i]==0) n/=fac[i],fac[cnt++]=fac[i];}
if (n<=psize) {
for (;n!=1;n/=p[n]) fac[cnt++]=p[n];
return;
}
if (miller(n)) fac[cnt++]=n;
else {
ll x=rho(n);
_factor(x);_factor(n/x);
}
}
void dfs(ll x,int dep) {
if (dep==_cnt) d.pb(x);
else {
dfs(x,dep+1);
for (int i=1;i<=_e[dep];i++) dfs(x*=_pr[dep],dep+1);
}
}
void norm() {
sort(fac,fac+cnt);
_cnt=0;
rep(i,0,cnt) if (i==0||fac[i]!=fac[i-1]) _pr[_cnt]=fac[i],_e[_cnt++]=1;
else _e[_cnt-1]++;
}
vector<ll> getd() {
d.clear();
dfs(1,0);
return d;
}
vector<ll> factor(ll n) {
cnt=0;
_factor(n);
norm();
return getd();
}
vector<PLL> factorG(ll n) {
cnt=0;
_factor(n);
norm();
vector<PLL> d;
rep(i,0,_cnt) d.pb(mp(_pr[i],_e[i]));
return d;
}
bool is_primitive(ll a,ll p) {
assert(miller(p));
vector<PLL> D=factorG(p-1);
rep(i,0,SZ(D)) if (powl(a,(p-1)/D[i].fi,p)==1) return 0;
return 1;
}
int findorder(ll a,ll p) {
assert(miller(p));
vector<PLL> D=factorG(p-1);
int t=p-1;
rep(i,0,SZ(D)) {
while (t%D[i].fi==0&&powl(a,t/D[i].fi,p)==1) t/=D[i].fi;
}
return t;
}
}
int _,p;
ll n,m;
int main() {
Factor::init(100000);
for (scanf("%d",&_);_;_--) {
scanf("%d%lld%lld",&p,&n,&m);
if (p==2||p==5) {
puts("0");
continue;
}
if (p==3) {
printf("%lld\n",m*(n/3));
continue;
}
ll x=Factor::findorder(10,p);
vector<PLL> dd=Factor::factorG(x);
ll ans=0;
for (int i=1;i<=m;i++) {
ll y=1;
int me=0;
for (auto q:dd) {
int e=(q.se+i-1)/i;
me=max(me,e);
rep(j,0,e) y=y*q.fi;
}
if (me==1) {
ans+=(n/y)*(m-i+1);
break;
} else {
ans+=n/y;
}
}
printf("%lld\n",ans);
}
}
最新文章
- ubuntu 13.10 monodevelop3 安装
- 只用css来美化的上传表单按钮（抄的迅雷的）
- UVA 10817 十一 Headmaster's Headache
- 使用Maven搭建Struts2+Spring3+Hibernate4的整合开发环境
- Codeforces 445 A DZY Loves Chessboard【DFS】
- 成功获取并更改中兴F660光猫的超级用户密码解除四台限制
- opencv人脸检测分类器训练小结
- ADO.NET 快速入门（六）：读写 XML
- ASP.NET实现折线图的绘制
- 从设计模式说起JAVA I/O流
- HTML5+CSS3正式开课
- 机房收费系统总结之4——VB.NET 轻松解决判断文本框、组合框为空问题
- PHP数组实际占用内存大小的分析
- 移动端的一些常用meta标签
- Nginx 怎么给一台服务器，配置两个域名？详细的解说+截图教程
- 方便快捷的求导求积分解方程在线工具sage介绍
- Code Generation => Table -> Class for DataGridView use
- 【题解】JSOIWC2019 Round 5
- python 全栈开发，Day75(Django与Ajax,文件上传,ajax发送json数据,基于Ajax的文件上传,SweetAlert插件)
- MySQL global Log