#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define X 10005
#define inf 0x3f3f3f3f
#define PI 3.141592653589793238462643383
int K;
const int N = 100000 + 5;
ll n,k,a,b,m,mod;
ll Pow(ll a,ll b)
{ll ans=1;while(b){if(b&1){ans=(ans*a)%mod;}b>>=1;a=(a*a)%mod;}return ans;
}
int main()
{while(~scanf("%lld%lld",&n,&k)){if(n==0&&k==0){break;}mod=k*250;a=Pow(2,3*n+1)-1;b=Pow(251,n+1)-1;m=(a*b)%(250*k)/250;mod=mod/250;printf("%d\n",Pow(2008,m));}return 0;
}
正解：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define X 10005
#define inf 0x3f3f3f3f
#define PI 3.141592653589793238462643383
int K,mod;
ll Pow(int a,int b)
{ll ans=1;while(b){if(b&1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans%mod;
}
void e_gcd(int a,int b,int &d,int &x,int &y)
{if(!b)d=a,x=1,y=0;elsee_gcd(b,a%b,d,y,x),y-=a/b*x;
}
ll inv(ll a,ll m)
{int d,x,y;e_gcd(a,m,d,x,y);return d==1?(x+m)%m:-1;
}
int main()
{ios::sync_with_stdio(false);int N;while(cin>>N>>K){if(N==K&&K==0)break;ll a,b;ll c=inv(250,K),m;if(c==-1){mod=K*250;a=Pow(2,3*N+1)-1;b=Pow(251,N+1)-1;m=((a*b)%(K*250))/250;mod/=250;printf("%d\n",Pow(2008,m));}else{mod=K;a=Pow(2,3*N+1)-1,b=Pow(251,N+1)-1;m=a*b*c%K;cout<<Pow(2008,m)<<endl;}}return 0;
}
A[i] = -(p / i) * A[p % i]; 对b进行求解逆元的的充要条件是b和模数m互质gcd(b,m)=1， 设c为b的逆元:bc≡1 mod p (bc+kp=1):bc对p取余为1(p>1) a/b%p=a/b*1=(a/b)*bc mod p=ac mod p 解释为：除以一个数对p取模等于乘以这个数的逆元对p取模 c=inv(b)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod=29;
ll Pow(int x,int n)
{ll ans=1;while(n){if(n&1)ans=(ans*x)%mod;x=(x*x)%mod;n>>=1;}return ans;
}
void e_gcd(int a,int b,int &d, int &x,int &y)
{if(!b)d=a,x=1,y=0;elsee_gcd(b,a%b,d,y,x),y-=a/b*x;
}
int inv(int a,int m)
{int d,x,y;e_gcd(a,m,d,x,y);return d==1?(x+m)%m:-1;
}
int main()
{ll x;while(scanf("%lld",&x)&&x){ll a=Pow(2,2*x+1)-1,b=Pow(3,x+1)-1,c=Pow(167,x+1)-1;//在函数名称上找bug找了半小时powcout<<(a*b*c*inv(2*166,mod))%mod<<endl;;}return 0;
}
HDU1098
f(x)=5*x^13+13*x^5+k*a*x 对给定的k，找到最小的a使得任意的x都%65=0成立 那么逆思维 对于f(1) 不管a是不是最小，那么是一定成立的，则（18+ka)%65=0 在根据这个公式找出最小的 a , 这道题很有趣的思维是 关于取余的一个循环 (18%65 + ka % 65 )%65 当 a=66的时候 又会出现 (18%65 + ka % 65 )%65 ,说明存在一个循环节
#include <bits/stdc++.h>
#define X 10005
#define inF 0x3f3f3f3f
#define PI 3.141592653589793238462643383
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
const int N = 1e4;
const int Times=10;
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int k;while(cin>>k){int i=1;int ans=18%65;for( i=1;i<66;++i){if((ans+k*i)%65==0){cout<<i<<endl;break;}}if(i==66)cout<<"no"<<endl;}return 0;
}
A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). Input The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed. Output For each test case, print the value of f(n) on a single line. Sample Input 1 1 3 1 2 10 0 0 0 Sample Output 2 5
一道矩阵快速幂的题：
递推： | A 1| (fn,fn-1)=(fn-1,fn-2) | | | B 0| | A 1| 最后fn=(f1,f2)*| | ^(n-2) | B 0|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{int A,B;ll n;int a[100]={1,1},t;while(scanf("%d%d%lld",&A,&B,&n),A||B||n){int i;for( i=2;i<50;++i)//这个50换成100竟然wa，不知道数据怎么设置的{a[i]=(A*a[i-1]+B*a[i-2])%7;if(a[i]==1&&a[i-1]==1){break;}}int t=i-2+1;printf("%d\n",n%t==0?a[t-1]:a[n%t-1]);}return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define X 10005
#define inf 0x3f3f3f3f
#define one 0x01
#define PI 3.141592653589793238462643383
const int N=1e6;
int mod=2009;
ll f[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n ,k;while(cin>>n>>k){ll sum=n*k;ll len=min(n,k);///n<k 算到n k<n 算到kll ans=0;for(int i=1;i<=len;++i){ll d=k/i;ll number=k/d;if(number>len)number=len;// cout<<i<<' '<<d<<' '<<number<<' '<<(d*(i+number)*(number-i+1)/2)<<endl;ans+=(d*(i+number)*(number-i+1)/2);i=number;}cout<<sum-ans<<endl;}return 0;
}
HDU2136 题目大意：求一个数的最大素数因子在素数序列中排第几。 总结：Everybody knows any number can be combined by the prime number.每个数都可以由一个素数结合起来(素数本身由自己和1组成，质数则可由一个素数和其他的数乘积得到 每个数都可以由一个若干个素数组成 T:
#include<bits/stdc++.h>
const int N=1000000;
using namespace std;int primer[N],po[N],cnt=0;
int main()
{po[cnt++]=1;for(int i=2;i<N;++i){if(!primer[i]){po[cnt++]=i;for(int j=i*2;j<N;j+=i){primer[j]=1;}}}int n;while(~scanf("%d",&n)){for(int i=n;i>=0;--i){if(po[i]<=n)//po[n]>n{if(n%po[i]==0){printf("%d\n",i);break;}}}}return 0;
}
正解：
#include<bits/stdc++.h>
const int N=1e6;
using namespace std;int primer[N],cnt=0;
int main()
{for(int i=2;i<N;++i){if(!primer[i]){primer[i]=++cnt;for(int j=2*i;j<N;j+=i){primer[j]=cnt;}}}int n;while(~scanf("%d",&n)){printf("%d\n",primer[n]);}return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define X 10005
#define inf 0x3f3f3f3f
#define one 0x01
#define PI 3.141592653589793238462643383
const int N=1e6;
int mod=2009;
ll f[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);f[0]=1;for(int i=1;i<=40;++i){f[i]=(i*f[i-1])%mod;// cout<<i<<' '<<f[i]<<endl;}// cout<<41*245%2009<<endl;ll n;while(cin>>n){if(n<41)cout<<f[n]<<endl;elsecout<<0<<endl;}return 0;
}
