扩展欧几里得和乘法逆元,欧拉函数 例题总结

1.洗牌：解 2^m*x同余l(mod  (n+1))

因为m和x、n+1数据范围都比较大，所以肯定要化简2^m

不能用拓展欧几里得！a^b三a^b mod(fai(n+1)),因为2^m还乘了一个x,2^m、l不一定同余于(n+1)\

但是可以先把2^m mod(n+1)算出来（等价于2^m），最后解方程

这样是等价的（可以手摸一下）

/*
递推解决一部分：
int local,cnt
while(cnt--)
{
if(local&1)
{local=local+1  /2;
local=(total/2+local)
}
if(偶数)
{
local=local/2;
local=(total/2+local);
}
}循环吧 

x*2^m 同余last mod(n+1)
求一下fai(n+1)//
然后m mod(fai(n+1))减小运算次数
a=(2^m)  x =最终答案
b=(n+1)  y=无所谓
k=last  算吧 
 */
 ll n,m,l;
 ll fai(ll x)
 {
 	ll ans=x,start=sqrt(x+1);
 	_f(i,2,start)
 	{
 		if(x%i==0)
 		{
 			ans=ans-ans/i;
 			while(x%i==0)x/=i;
		 }
	}
	if(n!=1)ans=ans-ans/n;
		return ans;
 }
 ll x,y;
ll exgcd(ll a,ll b)
 {
 	if(b==0)
 	{
 		x=1,y=0;return a;
	 }
ll res=exgcd(b,a%b);
ll t=x;x=y;y=(ll)t-(ll)a/b*y;return res;
  } 
ll pw(ll t)//2^t
{
  	ll ans=1;ll jie=2;
  	while(t)
  	{
  		if(t&1)ans=ans*jie%(n+1);
  		jie=jie*jie%(n+1);
  		t>>=1;
	  }
	  return ans;
}
int main()
{
	//freopen("exam.txt","r",stdin);
n=re(),m=re(),l=re();
//ll fai_n=fai(n+1);
//	m=m%fai_n;//估计用到long long 
	ll a=1,b=(n+1);
	a=pw(m);
ll gcd=exgcd(a,b);//
	x=(x*(l/gcd)%(b/gcd)+b/gcd)%(b/gcd);
//	if(x==0)x+=b/gcd;
	chu("%lld",x); 
	return 0;
}

2.仪仗队
欧拉函数性质和计算
性质:【要求一个指数数字的fai】fai(p^k)=p^k-p^(k-1)     如果p是素数(因为要把能整除p^k的数表示成p*t)
      【求一堆数字的fai】如果a mod b==0   fai(a*b)=b*fai(a)   把fai(a*b)拆开
　　　　　　　　　　　　　　　　　　　!=0  fai(a*b)=(b-1)*fai(a)
代码见霹雳虎
3.求gcd(1-n,n)之和
分析问题，简化问题，提高效率的思想
开始 想到暴力枚举 60分
想：不如求出所有以x为gcd的数的个数，最后num[i]*i直接搞定,(找的时候把未知当作已知，gcd(n,x)=now,同除now,gcd(n/now,x/now)=1,
不就是找n/now的fai吗，now一定是n的因子，所以找n的因子就行了)
90分
优化：找n的因子 1-sqrt(n),记得去掉重复的i*i

#include
#include
typedef long long ll;
ll euler(ll x)//欧拉函数
{
ll ans=x,tp=sqrt(x);
for(ll i=2;i<=tp;++i)
if(x%i==0)
{
ans=ans-ans/i;
while(x%i==0) x/=i;
}
if(x>1) ans=ans-ans/x;
return ans;
}
int main()
{
ll n;
scanf("%lld",&n);
ll ans=0,tp=sqrt(n);


for(ll i=1;i<=tp;++i)
if(n%i==0) ans+=i*euler(n/i)+n/i*euler(i);
if(tp*tp==n) ans-=tp*euler(tp);
printf("%lld\n",ans);
return 0;
}