题目链接

经典一个系列四道题，其他三道都是 trash。给定一个有一些位置初始被染色的矩阵，每次可以选择一行将一个公差为奇素数的等差序列位置染色，求最少操作多少次使得整个矩阵被染上色。

首先行和行之间是独立的，所以分别计算。显然一行如果初始都被染色，那么染色 \(0\) 次即可。因为有最小奇素数 \(3\)，所以一行最多被操作三次，下面考虑如何判断是一次还是两次。

注意到两个未被染色的位置如果间隔不是一个 \(2\) 的整次幂，那么这个间隔的距离一定含有至少一个奇素数因子。如果只有一个位置或者所有的位置间隔距离都含有同一个奇素因子，那么只需要染一次。否则我们尝试先染掉一个颜色，再看剩下的位置能否一次染完，这样就需要枚举奇素因子。记一行有 \(k\) 个位置未被染色，注意到只需要枚举 \(p_2 - p_1,p_k - p_1,p_k - p_2\) 的素因子，因为只会有从 \(p_1\) 出发染一趟，再从后面某一个位置出发染一趟这一种情况。于是做到 \(\mathcal O(nm \sigma(m))\)，其中 \(\sigma\) 是素因子个数，不会超过 \(7\) 个，提前线筛处理好即可。

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
 
namespace FastIO
{
    template<typename T=int> inline T read()
    {
        T s=0,w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*w;
    }
    template<typename T> inline void read(T &s)
    {
        s=0; int w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s=s*w;
    }
    template<typename T,typename... Args> inline void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename T> inline void write(T x,char ch)
    {
        if(x<0) x=-x,putchar('-');
        static char stk[25]; int top=0;
        do {stk[top++]=x%10+'0',x/=10;} while(x);
        while(top) putchar(stk[--top]);
        if(ch!='~') putchar(ch);
        return;
    }
}
using namespace FastIO;

namespace MTool
{   
    #define TA template<typename T,typename... Args>
    #define TT template<typename T>
    static const int Mod=1e9+7;
    TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
    TT inline void cmax(T &a,T b) {a=max(a,b);}
    TT inline void cmin(T &a,T b) {a=min(a,b);}
    TA inline void cmax(T &a,T b,Args... args) {a=max({a,b,args...});}
    TA inline void cmin(T &a,T b,Args... args) {a=min({a,b,args...});}
    TT inline void Madd(T &a,T b) {a=a+b>=Mod?a+b-Mod:a+b;}
    TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
    TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
    TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
    TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
    TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
    TT inline T Cmul(T a,T b) {return a*b%Mod;}
    TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
    TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
    TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
    TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
    TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
    TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
    TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
    TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
    TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
    TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
    TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
    TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
    #undef TT
    #undef TA
}
using namespace MTool;
 
inline void file()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    return;
}
 
bool Mbe;
 
namespace LgxTpre
{
    static const int MAX=100010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,m,ans;
    char s[MAX];
    
    namespace Sieve
    {
    	constexpr int N=100000;
    	int vis[N+10],P[MAX],Pcnt;
    	vector<int> fac[MAX];
	    inline void Init()
	    {
	        for(int i=2;i<=N;++i)
	        {
	            if(!vis[i]) P[++Pcnt]=i;
	            for(int j=1;j<=Pcnt&&i*P[j]<=N;++j) {vis[i*P[j]]=1; if(!i%P[j]) break;}
	    	}
	    	for(int i=2;i<=Pcnt;++i) for(int j=P[i];j<=N;j+=P[i]) fac[j].eb(P[i]);
		}
	}
	using namespace Sieve;
	
	namespace BinaryGCD
	{
		int gcd(int a,int b)
	    {
	    	int az=__builtin_ctz(a),bz=__builtin_ctz(b);
	    	int z=min(az,bz),tmp; b>>=bz;
	    	while(a) a>>=az,tmp=a-b,az=__builtin_ctz(tmp),b=min(a,b),a=abs(tmp);
	    	return b<<z;
		}
	}
    
    inline void lmy_forever()
    {
    	auto solve=[&]()->int
    	{
    		auto chk=[&]()->bool
    		{
    			vector<int> q;
    			for(int i=1;i<=m;++i) if(s[i]=='.') q.eb(i);
    			if(((int)q.size())<=1) return 1;
    			int g=q[1]-q[0];
    			for(int i=2;i<((int)q.size());++i) g=BinaryGCD::gcd(g,q[i]-q[i-1]);
    			return __builtin_popcount(g)==1?0:1;
			};
			
    		auto change=[&](int f0,int f1)->int
    		{
				bool flag=0;
				for(auto f:fac[f1-f0])
				{
					for(int i=f0;i<=m;i+=f) if(s[i]=='.') s[i]='?';
					if(chk()) flag=1;
					for(int i=f0;i<=m;i+=f) if(s[i]=='?') s[i]='.';
					if(flag) return 2;
				}
				return 3;
			};
    		
    		vector<int> p;
    		for(int i=1;i<=m;++i) if(s[i]=='.') p.eb(i);
    		if(((int)p.size())<=1) return p.size();
    		if(((int)p.size())==2) return __builtin_popcount(p[1]-p[0])==1?2:1;
    		if(chk()) return 1;
    		int dif=3;
    		cmin(dif,change(p[0],p[1])),cmin(dif,change(p[0],p.back())),cmin(dif,change(p[1],p.back()));
    		return dif;
		};
    	
    	Init(),read(n,m);
    	for(int i=1;i<=n;++i) scanf("%s",s+1),ans+=solve();
    	write(ans,'\n');
	}
}

bool Med;

signed main() 
{
//  file();
    fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
    int Tbe=clock();
    LgxTpre::lmy_forever();
    int Ted=clock();
    cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}