Problem A

Description:

Input

1≤N≤1,000

1≤len(string)≤100,000

1≤a,b≤len(string)
Output

Sample Input
2
ACMlove2015
1 11
8 10
1
testMessage
1 1
Sample Output
6891
9240
88

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5+10;
ll xiaozhu[maxn];
const ll mod=9973;
ll poww(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1) ans=(ans*x)%mod;
x=(x*x)%mod;
y/=2;
}
return ans;
}
int main()
{
ll n,a,b;
string s;
while(cin>>n>>s)
{
ll x,y;
xiaozhu[0]=1;
for(ll i=0;i<s.size();i++)
xiaozhu[i+1]=((s[i]-28)*xiaozhu[i])%9973;
// for(lli=0;i<=s.size();i++)
//     cout<<xiaozhu[i]<<"?\n";
while(n--)
{
cin>>a>>b;
cout<<(xiaozhu[b]%mod)*(poww(xiaozhu[a-1],mod-2))%mod<<endl;;
}
}
}


A/B

Description:

Input

Output

Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=y;
y=x-(a/b)*y;
x=t;
return r;
}
int main()
{
int n,a,b,x,y;
cin>>n;
while(n--)
{
cin>>a>>b;
exgcd(b,9973,x,y);

cout<<((x*a)%9973+9973)%9973<<endl;
}
}


Fansblog

Description:
Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )
Input
First line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)
Output
For each testcase, output an integer representing the factorial of Q modulo P.
Sample Input
1
1000000007
Sample Output
328400734

Problem solving:

1. 逆元
2. 素数判断(更快地素数判断(可选))
3. 快速乘
4. 快速幂
5. 威尔逊定理
6. 快速幂

q!\*(q+1)\*(q+2)\*.......\*(p-1) % p = p-1

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll x)
{
for(ll i=2;i<=sqrt(x);i++)
if(x%i==0)    return 0;
return 1;
}
ll ksc(ll a,ll b,ll p)
{
return (a*b-(ll)((long double)a/p*b)*p+p)%p;
}
ll poww(ll a,ll b,ll p)
{
ll ans=1;
while(b)
{
if(b&1)    ans=ksc(ans,a,p);
b/=2;
a=ksc(a,a,p);
}
return ans;
}
ll inv(ll x,ll p)
{
return poww(x,p-2,p);
}
int main()
{
ios::sync_with_stdio(0);
int n;
cin>>n;
ll p;
while(n--)
{
cin>>p;
ll ans=p-1;
for(ll i=p-2;;i-=2)
{
if(check(i))
{
for(ll j=i+1;j<p;j++)
{
ans=ksc(ans,inv(j,p),p);
}
cout<<ans%p<<endl;
break;
}
}
}
}


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ksc(ll a,ll b,ll p)
{
return (a*b-(ll)((long double)a/p*b)*p+p)%p;
}
ll prime[5] = {2, 5, 3, 233, 331};
ll qpow(ll a,ll b,ll p)
{
ll ans = 1;
while (b)
{
if (b & 1) ans = ksc(ans,a,p);
b >>= 1;
a = ksc(a,a,p);
}
return ans;
}
bool Miller_Rabin(ll p)
{
if(p < 2) return 0;
if(p != 2 && p % 2 == 0) return 0;
ll s = p - 1;
while(! (s & 1)) s >>= 1;
for(int i = 0; i < 3; ++i)
{
if(p == prime[i]) return 1;
ll t = s, m = qpow(prime[i], s, p);
while(t != p - 1 && m != 1 && m != p - 1)
{
m = ksc(m, m, p);
t <<= 1;
}
if(m != p - 1 && !(t & 1)) return 0;
}
return 1;
}
ll inv(ll x,ll p)
{
return qpow(x,p-2,p);
}
int main()
{
ios::sync_with_stdio(false);
int t;
cout<<(12 %(-7))<<endl;
cin>>t;
while (t --)
{
ll p;
cin>>p;
ll ans = p-1;
for (ll x = p - 2;;x -= 2)
{
if (Miller_Rabin(x))
{
for (ll i = x + 1;i < p;i ++)
ans = ksc(ans,inv(i,p),p);
cout<<ans<<'\n';
break;
}
}
}
return 0;
}


Romantic

Description:
The Sky is Sprite.
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees
Trees are Shaking, Leaves are Falling.
Lovers Walk passing, and so are You.
................................Write in English class by yifenfei
Girls are clever and bright. In HDU every girl like math. Every girl like to solve math problem!
Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.
Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)
Output
output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put "sorry" instead.
Sample Input
77 51
10 44
34 79
Sample Output
2 -3
sorry
7 -3
Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
ll r=exgcd(b,a%b,x,y),t=y;
y=x-(a/b)*y,x=t;
return r;
}
int main()
{
ll a,b;
while(cin>>a>>b)
{
ll g=__gcd(a,b);
ll x,y;
exgcd(a,b,x,y);
if(a*x+b*y!=1)
{
puts("sorry");
continue;
}
if(b<0) b=-b;
x%=b;
while(x<0)
{
x+=b;
}
y=(1-a*x)/b;
cout<<x<<" "<<y<<endl;
}
}


Integer Divisibility

Description:
If an integer is not divisible by 2 or 5, some multiple of that number in decimal notation is a sequence of only a digit. Now you are given the number and the only allowable digit, you should report the number of digits of such multiple.

For example you have to find a multiple of 3 which contains only 1's. Then the result is 3 because is 111 (3-digit) divisible by 3. Similarly if you are finding some multiple of 7 which contains only 3's then, the result is 6, because 333333 is divisible by 7.

Input
Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case will contain two integers n (0 < n ≤ 1e6 and n will not be divisible by 2 or 5) and the allowable digit (1 ≤ digit ≤ 9).

Output
For each case, print the case number and the number of digits of such multiple. If several solutions are there; report the minimum one.

Sample Input
3
3 1
7 3
9901 1

Sample Output
Case 1: 3
Case 2: 6
Case 3: 12

Problem solving:

Code:

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int main()
{
int n;
ll a,b;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
int ans=0,mid=0;
ll p=1;
while(p)
{
mid=(mid*10+b)%a;
ans++;
p=mid;
}
printf("Case %d: %d\n",i,ans);
}
}


Large Division

Description:
Given two integers, a and b, you should check whether a is divisible by b or not. We know that an integer a is divisible by an integer b if and only if there exists an integer c such that a = b * c.

Input
Input starts with an integer T (≤ 525), denoting the number of test cases.

Each case starts with a line containing two integers a (-10^200 ≤ a ≤ 10^200) and b (|b| > 0, b fits into a 32 bit signed integer). Numbers will not contain leading zeroes.

Output
For each case, print the case number first. Then print 'divisible' if a is divisible by b. Otherwise print 'not divisible'.

Sample Input
6
101 101
0 67
-101 101
7678123668327637674887634 101
11010000000000000000 256
-202202202202000202202202 -101

Sample Output
Case 1: divisible
Case 2: divisible
Case 3: divisible
Case 4: not divisible
Case 5: divisible
Case 6: divisible

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,a;
string s;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s>>a;
printf("Case %d: ",i);
ll mid=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='-')   continue;
mid=(mid*10+s[i]-'0')%a;
}
if(mid) puts("not divisible");
else    puts("divisible");
}
}


青蛙的约会

Description:

Input

Output

Sample Input
1 2 3 4 5
Sample Output
4
Problem solving:

Code:





Candy Distribution

Description:
Kids like candies, so much that they start beating each other if the candies are not fairly distributed. So on your next party, you better start thinking before you buy the candies.

If there are K kids, we of course need K⋅X candies for a fair distribution, where X is a positive natural number. But we learned that always at least one kid looses one candy, so better be prepared with exactly one spare candy, resulting in (K⋅X)+1 candies.

Usually, the candies are packed into bags with a fixed number of candies C. We will buy some of these bags so that the above constraints are fulfilled.

Input
The first line gives the number of test cases t (0<t<100). Each test case is specified by two integers K and C on a single line, where K is the number of kids and C the number of candies in one bag (1≤K,C≤1e9). As you money is limited, you will never buy more than 1e9 candy bags.

Output
For each test case, print one line. If there is no such number of candy bugs to fulfill the above constraints, print “IMPOSSIBLE” instead. Otherwise print the number of candy bags, you want to buy. If there is more than one solution, any will do.

Sample Input 1 Sample Output 1
5
10 5
10 7
1337 23
123454321 42
999999937 142857133
IMPOSSIBLE
3
872
14696943
166666655

Problem solving:

{a代表的是每蓝糖果的个数，x代表的是买了几蓝，b代表的是热人数，y代表的是每个人分到的糖果的个数}

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if (!b)
{
x = 1,y = 0;
return a;
}
int r = exgcd(b,a%b,x,y);
int tmp = y;
y = x - (a / b) * y;
x = tmp;
return r;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,b;
ll x,y;
cin>>a>>b;
ll mid=exgcd(a,b,x,y);
if(mid!=1)    puts("IMPOSSIBLE");
else
{
if(b==1)
{
cout<<a+1<<endl;
continue;
}
while(y<=0)    y+=a;
cout<<y<<endl;
}
}
return 0;
}