description
设矩阵 R R R 是由若干个正方形所组成的矩阵,定义函数 F ( R ) F(R) F(R) 为矩阵 R R R 的某一条对角线穿过的小正方形的个数。现在已知 F ( R ) = N F(R)=N F(R)=N,求可能的矩阵 R R R 的个数。
n ≤ 1 0 9 n\leq 10^9 n≤109,数据随机生成
solution 设一个矩形 R = n × m , m ≤ n R=n\times m,m\leq n R=n×m,m≤n,显然他对角线经过了 gcd ( n , m ) − 1 \gcd(n,m)-1 gcd(n,m)−1 个格点,把他分成了 gcd ( n , m ) \gcd(n,m) gcd(n,m) 个相同的小矩形。
那么我们只需要考虑一个 n gcd ( n , m ) × m gcd ( n , m ) \dfrac{n}{\gcd(n,m)}\times\dfrac{m}{\gcd(n,m)} gcd(n,m)n×gcd(n,m)m 的矩形的交点个数
我们发现他在纵方向上显然至少要经过 n gcd ( n , m ) \dfrac{n}{\gcd(n,m)} gcd(n,m)n 个格子,而纵坐标方向因为不交在格点上,所以只会多增加 m gcd ( n , m ) − 1 \dfrac{m}{\gcd(n,m)}-1 gcd(n,m)m−1 个格子
所以我们可以推出
F ( R ) = gcd ( n , m ) × ( n gcd ( n , m ) + m gcd ( n , m ) − 1 ) = n + m − gcd ( n , m ) F(R)=\gcd(n,m)\times(\dfrac{n}{\gcd(n,m)}+\dfrac{m}{\gcd(n,m)}-1)=n+m-\gcd(n,m) F(R)=gcd(n,m)×(gcd(n,m)n+gcd(n,m)m−1)=n+m−gcd(n,m)
已知 F ( R ) = N F(R)=N F(R)=N
也就是 n + m − gcd ( n , m ) = N n+m-\gcd(n,m)=N n+m−gcd(n,m)=N
发现枚举 gcd 的话时间会炸,所以我们考虑把 gcd 除掉
n gcd ( n , m ) + m gcd ( n , m ) − 1 = N gcd ( n , m ) \dfrac{n}{\gcd(n,m)}+\dfrac{m}{\gcd(n,m)}-1=\dfrac{N}{\gcd(n,m)} gcd(n,m)n+gcd(n,m)m−1=gcd(n,m)N
也就是 gcd ( n , m ) \gcd(n,m) gcd(n,m) 只有可能是 N N N 的因数。
设 f ( x ) f(x) f(x) 表示 i + j = x , gcd ( i , j ) = 1 i+j=x,\gcd(i,j)=1 i+j=x,gcd(i,j)=1 的 ( i , j ) (i,j) (i,j) 的个数,那么问题转化成了求
∑ d ∣ N f ( d + 1 ) \sum_{d|N}f(d+1) d∣N∑f(d+1)
考虑如何求 f ( x ) f(x) f(x)。观察发现,如果 gcd ( i , x ) = 1 \gcd(i,x)=1 gcd(i,x)=1 时,显然满足条件, 否则不满足条件,也就是转化成了求与 x x x 互质的数的个数,即 f ( x ) = ϕ ( x ) f(x)=\phi(x) f(x)=ϕ(x)
也就是转化成了求
∑ d ∣ N ϕ ( d + 1 ) \sum_{d|N}\phi(d+1) d∣N∑ϕ(d+1)
我们枚举 N N N 的因数,每次暴力计算,复杂度是 O ( d ( n ) ⋅ n ) O(d(n)\cdot \sqrt n) O(d(n)⋅n ),其中 d ( n ) d(n) d(n) 表示 n n n 的因数个数,计算发现 1 0 9 10^9 109 内因数个数最多的也只有 1300 多个,并且很难跑满,加上数据随机生成,就可以通过了。
code
#include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(int i=a;i<=b;i++) # define _Rep(i,a,b) for(int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=1e4+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } ll n; int fac[N],tot; ll ans; ll phi(int x){ ll res=x; for(int i=2;i*i<=x;i++){ if(x%i==0)res=res/i*(i-1); while(x%i==0)x/=i; } if(x>1)res=res/x*(x-1); return res; } int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); read(n); for(int i=1;i*i<=n;i++){ if(n%i==0){ fac[++tot]=i; if(n/i!=i)fac[++tot]=n/i; } } Rep(i,1,tot)ans+=phi(n/fac[i]+1); printf("%lld\n",(ans+1)/2); return 0; }description
给出一个长度为 N N N 的正整数数列 { A i } \{A_i\} {Ai},现在可以给数列中的每个数加上任意的正整数增量,也可以不加,给一个数加上 X X X 的代价为 X 2 X^2 X2。在修正后的数列中,计算每两个相邻整数的差的绝对值,将它乘以 C C C 计入代价中。求最小代价。
n ≤ 1 0 5 n\leq 10^5 n≤105
solution
首先考虑 3 3 3 个数的最简单情况,我们想要修改中间的数的条件应该是 a i − 1 > a i < a i + 1 a_{i-1}>a_i<a_{i+1} ai−1>ai<ai+1,否则修改代价增加,差值代价不变,显然不优。
同时我们发现, a i a_i ai的最终取值范围应当在 [ a i , min ( a i − 1 , a i + 1 ) ] [a_i,\min(a_{i-1},a_{i+1})] [ai,min(ai−1,ai+1)] 上,如果再变大,修改代价增加,差值代价不变,显然不优。
考虑 4 4 4 个数的时候,同样的,中间能够被修改的前提也是两边比他大。
考虑中间被修改的值能够是多少,假设中间两个数调整后 B < C B<C B<C,那么把 C − 1 C-1 C−1,修改代价减小,差值代价不变,显然更优。
我们可以证明,对于一个区间 [ i , j ] [i,j] [i,j] 能够被修改的条件,就是 RMQ ( i + 1 , j − 1 ) ≤ min ( a i , a j ) \operatorname{RMQ}(i+1,j-1)\leq \min(a_i,a_j) RMQ(i+1,j−1)≤min(ai,aj),并且 [ i + 1 , j − 1 ] [i+1,j-1] [i+1,j−1] 之间的数修改完的值相等,且在 [ RMQ ( i + 1 , j − 1 ) , min ( a i , a j ) ] [\operatorname{RMQ}(i+1,j-1),\min(a_i,a_j)] [RMQ(i+1,j−1),min(ai,aj)] 上。
那么如何确定在哪里取最小值呢?我们把它写成一个函数的形式,假设这个区间为 [ l , r ] [l,r] [l,r],最后高度为 x x x,代价为 y y y
y = ( r − l − 1 ) x 2 − ( 2 ∑ i = l + 1 r − 1 a i − 2 c ) x + ( a i + a j ) c + ∑ i = l + 1 r − 1 a i 2 y=(r-l-1)x^2-(2\sum_{i=l+1}^{r-1}a_i-2c)x+(a_i+a_j)c+\sum_{i=l+1}^{r-1}a_i^2 y=(r−l−1)x2−(2i=l+1∑r−1ai−2c)x+(ai+aj)c+i=l+1∑r−1ai2
相当于转化成二次函数的最值问题。
同时我们发现,这个转移对于每一个 i i i 是只能从 j j j 满足 RMQ ( i + 1 , j − 1 ) ≤ min ( a i , a j ) \operatorname{RMQ}(i+1,j-1)\leq \min(a_i,a_j) RMQ(i+1,j−1)≤min(ai,aj) 转移过来的,这个是满足单调栈性质的,所以我们可以用一个单调栈来进行维护转移一个 d p dp dp。
注意边界问题和一些细节。
复杂度 O ( n log n + n ) O(n\log n+n) O(nlogn+n)
#include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(int i=a;i<=b;i++) # define _Rep(i,a,b) for(int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=1e5+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } int n,m; int a[N]; ll f[N]; int st[N][20],lg[N]; ll sum1[N],sum2[N]; int s[N],top; int RMQ(int l,int r){ int len=r-l+1; return max(st[l][lg[len]],st[r-(1<<lg[len])+1][lg[len]]); } ll cost(int l,int r){ if(r==l+1)return 1ll*m*abs(a[r]-a[l]); ll A=r-1-l,B=-2*(sum1[r-1]-sum1[l]),C=sum2[r-1]-sum2[l]; if(l!=0)B-=m,C+=1ll*a[l]*m; if(r!=n+1)B-=m,C+=1ll*a[r]*m; int mn=RMQ(l+1,r-1),mx=min(a[l],a[r]); ll ver=-B/(2*A),res=1e18; Rep(i,-1,1) if(ver+i>=mn&&ver+i<=mx)res=min(res,A*(ver+i)*(ver+i)+B*(ver+i)+C); res=min(res,A*mn*mn+B*mn+C); res=min(res,A*mx*mx+B*mx+C); return res; } int main() { freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); memset(f,0x3f,sizeof(f)); read(n),read(m); Rep(i,1,n)read(a[i]); lg[1]=0; Rep(i,2,n)lg[i]=lg[i>>1]+1; Rep(i,1,n)st[i][0]=a[i]; Rep(j,1,19) Rep(i,1,n) if(i+(1<<j-1)<=n)st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]); Rep(i,1,n)sum1[i]=sum1[i-1]+a[i]; Rep(i,1,n)sum2[i]=sum2[i-1]+1ll*a[i]*a[i]; a[0]=a[n+1]=1e9; s[++top]=0; s[++top]=1; f[0]=f[1]=0; Rep(i,2,n+1){ if(i!=n+1)f[i]=min(f[i],f[i-1]+1ll*m*abs(a[i]-a[i-1])); else f[i]=f[i-1]; while(a[s[top]]<a[i]){ f[i]=min(f[i],f[s[top]]+cost(s[top],i)); top--; } f[i]=min(f[i],f[s[top]]+cost(s[top],i)); s[++top]=i; } printf("%lld\n",f[n+1]); return 0; }